Points in rectangle
发布时间
阅读量：
阅读量
Points in rectangle
单点时限: 2.0 sec
内存限制: 512 MB
在二维平面内存在一个矩形，在其四个顶点分别标有坐标(0,a)、(a,0)、(n,n−a)以及(n−a,n)。目前你拥有m个点，请问其中有多少个点位于这个矩形内部（包括边界）？
请指定n和a的值（其中a必须小于n且都不超过103）。接着给出一个正整数m（范围在1到103之间），它表示所给点的数量。随后是m组数据（共m行），每组数据包含两个整数x_i和y_i（它们都在1到103之间）。
首先，在第一行中输出矩形内点的数量；接着，在每一行中按照以下规则依次输出每个点的坐标：按照横坐标的大小排序；当两个点具有相同的横坐标时，则比较它们的纵坐标的大小；如果没有符合条件的数据，则以-1表示。
样例
input
6 1
5
1 2
1 3
2 3
3 4
4 5
output
4
4 5
3 4
2 3
1 2
解决这个问题的方法就是计算点到四条直线的距离。当这些距离全部不超过每条边对应的临界值时，则将该点加入集合中。
就是在找四条边的斜率的时候脑子又宕机了。。。把斜率搞反了。。。
ac代码
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n,a,m;
struct xy{
int x,y;
};
xy e1[1005],e2[1005];
bool cmp(xy a,xy b){
if(a.x ==b.x ) return a.y >b.y ;
else return a.x >b.x ;
}
bool changdu1(int a1,int b1){
int l;
l=abs(a1+b1-a);
//cout<<"111 "<<l<<" "<<abs((n-a)*2)<<endl;
if(l<=abs(a-n)*2) return 1;
else return 0;
}
bool changdu2(int a1,int b1){
int l;
l=abs(a1+b1-2*n+a);
//cout<<"222 "<<l<<" "<<abs((n-a)*2)<<endl;
if(l<=abs(a-n)*2) return 1;
else return 0;
}
bool changdu3(int a1,int b1){
int l;
l=abs(a1-b1+a);
//cout<<"333 "<<l<<" "<<abs(a*2)<<endl;
if(l<=abs(a*2)) return 1;
else return 0;
}
bool changdu4(int a1,int b1){
int l;
l=abs(a1-b1-a);
//cout<<"444 "<<l<<" "<<abs(a*2)<<endl;
if(l<=abs(a*2)) return 1;
else return 0;
}
int main(){
cin>>n>>a;
cin>>m;
for(int i=0;i<m;i++){
cin>>e1[i].x>>e1[i].y ;
}
//sort(e1,e1+m,cmp);
int sum=0;
int x1,y1,x2,y2;
x1=min(0,n-a);
x2=max(a,n);
for(int i=0;i<m;i++){
if(e1[i].x >=x1&&e1[i].x <=x2&&e1[i].y >=x1&&e1[i].y <=x2){
//cout<<e1[i].x <<" "<<e1[i].y <<endl;
// cout<<changdu1(e1[i].x,e1[i].y)<<endl;
//cout<<changdu2(e1[i].x,e1[i].y)<<endl;
//cout<<changdu3(e1[i].x,e1[i].y)<<endl;
//cout<<changdu4(e1[i].x,e1[i].y)<<endl;
if(changdu1(e1[i].x,e1[i].y)&&changdu2(e1[i].x,e1[i].y)&&changdu3(e1[i].x,e1[i].y)&&changdu4(e1[i].x,e1[i].y)){
e2[sum].x=e1[i].x ;
e2[sum].y=e1[i].y ;
sum++;
}
}
}
sort(e2,e2+sum,cmp);
if(sum==0) cout<<"-1"<<endl;
else{
cout<<sum<<endl;
for(int i=0;i<sum;i++){
cout<<e2[i].x <<" "<<e2[i].y <<endl;
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~