SGU 124. Broken line 射线法 eps的精准运用,计算几何 难度:3

124. Broken line

time limit per test: 0.25 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 (X₀,Y₀) 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 integerx_i1,y_i1,x_i2,y_i2; 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 X₀ and Y₀ - the coordinates of the given point delimited by a space. (Numbers X₀, Y₀ in 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

因为线条简单,所以随便射线法就行了,射线的"稍微移动",也就是对目标区间做半开半闭处理,可以用eps实现,很巧妙 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1e-9;
struct pnt{
    double x,y;
    pnt():x(0),y(0){}
    pnt(double tx,double ty):x(tx),y(ty){}
}p[20000][2],aim;
int n;
bool onborder(int ind){
    if(fabs(p[ind][0].y-p[ind][1].y)>eps){
        int low=min(p[ind][0].y,p[ind][1].y);
        int high=max(p[ind][0].y,p[ind][1].y);
        if(fabs(aim.x-p[ind][0].x)>eps)return false;
        return aim.y>low+eps&&aim.y+eps<high;
    }
    else {
        int low=min(p[ind][0].x,p[ind][1].x);
        int high=max(p[ind][0].x,p[ind][1].x);
        if(fabs(aim.y-p[ind][0].y)>eps)return false;
        return aim.x+eps>low&&aim.x<high+eps;
    }
}
bool cross(int ind){
    if(fabs(p[ind][0].y-p[ind][1].y)<eps)return false;
    if(aim.x+eps>p[ind][0].x)return false;
    int low=min(p[ind][0].y,p[ind][1].y);
    int high=max(p[ind][0].y,p[ind][1].y);
    return aim.y+eps>low&&eps+aim.y<high;//ATTENTION aim.y>=low&&aim<high
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf%lf%lf",&p[i][0].x,&p[i][0].y,&p[i][1].x,&p[i][1].y);
    }
    scanf("%lf%lf",&aim.x,&aim.y);
    int cnt=0;
    for(int i=0;i<n;i++){
        if(onborder(i)){puts("BORDER");return 0;}
        else if(cross(i))cnt++;
    }
    if(cnt&1)puts("INSIDE");
    else puts("OUTSIDE");
    return 0;
}