题目描述:
124. Broken line
time limit per test: 0.5 sec.
memory limit per test: 4096 KB
There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of K segments. You have to determine, whether a given point with
coordinates (X0,Y0) is inside this closed broken line, outside or belongs to the broken line.
Input
The first line contains integer K (4
Ј
K Ј 10000) - the number of broken line segments. Each of the following N lines contains coordinates of the beginning and end
points of the segments (4 integer xi1,yi1,xi2,yi2; all numbers in a range from -10000 up to 10000 inclusive).
Number separate by a space. The segments are given in random order. Last line contains 2 integers
X0 and Y0- the coordinates of the given point delimited by a space. (Numbers
X0, Y0in a range from -10000 up to 10000 inclusive).
Output
The first line should contain:
INSIDE - if the point is inside closed broken line,
OUTSIDE - if the point is outside,
BORDER - if the point belongs to broken line.
Sample Input
4
0 0 0 3
3 3 3 0
0 3 3 3
3 0 0 0
2 2
Sample Output
INSIDE
一道比较简单的计算几何,就是求给定点是否在一个多边形内部,我们可以从这个点引出一条射线,计算其与所有边的交点,如果是奇数个,说明在内部,否则在外部。
那么我们取怎样的射线比较合适?
因为题目告诉我们边平行与坐标轴,我们可以取与Y正方向平行大致向左偏一点的射线,就可以避免其和平行于Y轴的边相交,这就是代码中 if(p[i].a.x<P.x&&p[i].b.x>=P.x)k++; 左边取小于号的原因。
附上AC代码:
#include<iostream> #include<cstring> #include<cstdio> #include<set> #include<algorithm> #include<vector> #include<cstdlib> #define inf 0xfffffff #define CLR(a,b) memset((a),(b),sizeof((a))) #define FOR(a,b) for(int a=1;a<=(b);(a)++) using namespace std; int const nMax = 10010; int const base = 10; typedef int LL; typedef pair<LL,LL> pij; struct point{ int x,y; bool operator <(const point& b)const { if(x==b.x)return y<b.y; else return x<b.x; } } P; struct seg{ point a,b; }; seg p[nMax]; int n; int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d%d%d",&p[i].a.x,&p[i].a.y,&p[i].b.x,&p[i].b.y); if(p[i].b<p[i].a)swap(p[i].a,p[i].b); } scanf("%d%d",&P.x,&P.y); int k=0; for(int i=0;i<n;i++){ if(p[i].a.x==p[i].b.x){ if(P.x==p[i].a.x&&P.y>=p[i].a.y&&P.y<=p[i].b.y){ printf("BORDER\n"); return 0; } }else { if(p[i].a.y==P.y&&p[i].a.x<=P.x&&p[i].b.x>=P.x){ printf("BORDER\n"); return 0; } } } for(int i=0;i<n;i++){ if(p[i].a.y==p[i].b.y&&p[i].a.y>P.y){ if(p[i].a.x<P.x&&p[i].b.x>=P.x)k++; } } if(k&1)printf("INSIDE\n"); else printf("OUTSIDE\n"); return 0; }