Closed Fences USACO 3.4(阵亡)

描述

一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有N个角(顶点) (3 < N < 200)。顶点不重合，它以逆时针方式以数组{x_i, y_i}给出(i=1,2,...,N)。

每一对相邻的顶点都是一条栅栏。因此共有N条栅栏 (定义x_N+1=x₁, y_N+1=y₁)。

这里有一个栅栏的例子和一个点x,y:

                        * x3,y3
                x5,y5  / 
   x,y *          *   /   
                 /  /     
                /   *       
          x6,y6*   x4,y4     
               |              
               |               
          x1,y1*----------------* x2,y2

请编写一个程序实现下面的任务:

检查输入的顶点列表{xi,yi}, i=1,2,...,N, 判断它是否为一个合法的闭合栅栏。
找出所有可以被站在点(x,y)处的人所能看到的栅栏(忽略人的高度)，因为有的栅栏会被另外的栅栏所挡住。

只有当存在从(x,y)发射的一条射线第一个穿过栅栏i时，栅栏i是可以被看见的。如果栅栏是平行于目光的，它并不认为是可以看见的。在上面的例子里，线段[x3,y3]-[x4,y4], [x5,y5]-[x6,y6], [x6-y6]-[x1,y1]是可以被(x,y)看见的。

[编辑]格式

PROGRAM NAME: fence4

INPUT FORMAT:

(file fence4.in)

第一行: N, 表示闭合栅栏的顶点数。

第二行: 两个整数x和y，表示观测者的位置。两个整数都是16位的。即2^16，在longlong或longint范围内。

第3到N+2行: 每行一对整数(x,y)表示对应闭合栅栏的第k个顶点的坐标。坐标以逆时针顺序给出。整数绝对值不超过1000。

注意：我添加了该题的新的第12个测试点。如果你认为这个点的数据是错误的，发送邮件到Rob（kolstad@ace.delos.com）在您的邮件主题中一定要包括USACO！

OUTPUT FORMAT:

(file fence4.out)

如果给出的序列不是一个合法的闭合栅栏，那么输出文件只需要输出“NOFENCE”。

输出能被看见的栅栏，栅栏用两端的顶点表示，顶点的输出顺序以输入文件中的顺序为准。把栅栏按照最后一个点在输入文件中的顺序排序。如果两条栅栏的最后一个点是一样的，就以它们第一个点的顺序排序。

[编辑]SAMPLE INPUT

[编辑]SAMPLE OUTPUT

7
0 0 7 0
5 2 7 5
7 5 5 7
5 7 3 5
-2 7 0 3
0 0 -3 1
0 3 -3 1

搞了好久搞不出来，先贴个大牛代码过了先

/*
ID: hubiao cave
PROG: fence4
LANG: C++
*/

#include<fstream>
#include<cmath>
using namespace std;
ofstream fout ("fence4.out",ios::out);
ifstream fin ("fence4.in",ios::in);
const double JD = 0.005;
struct Point{
    double x,y;
}point[201],see;
struct Line{
    Point start,end;
}line[201];
long n,len=0;
bool cansee[201],reg[201];
inline double crossproduct(Point start,Point U,Point V){//计算叉积
    double Ux=U.x-start.x,Uy=U.y-start.y,Vx=V.x-start.x,Vy=V.y-start.y;
    return (Ux*Vy-Uy*Vx);
}
inline int cancross(Line A,Line B){
    double A1=crossproduct(A.start,A.end,B.start),A2=crossproduct(A.start,A.end,B.end),
        B1=crossproduct(B.start,B.end,A.start),B2=crossproduct(B.start,B.end,A.end);
    if(A1==0 || A2==0) return -1;//被点挡住
    if(A1*A2<0 && B2*B1<0) return 1;//严格相交
    return 0;
}
inline bool check(const Line &mid){
    for(int i=1;i<=n;i++) if(!reg[i])
        if(cancross(mid,line[i])!=0) return false;
    return true;
}
inline bool watch(Point start,Point end){
    if(sqrt(((start.x-end.x)*(start.x-end.x))+((start.y-end.y)*(start.y-end.y)))<JD) return false;
    Line mid;//中位线
    bool temp=false;
    mid.end.x=(start.x+end.x)/2;
    mid.end.y=(end.y+start.y)/2;
    mid.start.x=see.x;
    mid.start.y=see.y;
    if(check(mid)) return true;
    else{
        temp=watch(start,mid.end);
        if(!temp) temp=watch(mid.end,end);
    }
    return temp;
}
int main()
{
    fin>>n>>see.x>>see.y;
    fin>>point[1].x>>point[1].y;
    for(int i=1;i<=200;i++) cansee[i]=false;
    for(int i=2;i<=n;i++){
        fin>>point[i].x>>point[i].y;
        line[i-1].start=point[i-1];
        line[i-1].end=point[i];
    }
    line[n].start=point[1];
    line[n].end=point[n];
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(cancross(line[i],line[j])==1){fout<<"NOFENCE"<<endl;return 0;}
    for(int i=1;i<=n;i++){
        if(crossproduct(see,line[i].start,line[i].end)==0) continue;
        reg[i]=true;//不要跟自己比较
        if(watch(line[i].start,line[i].end)){len++; cansee[i]=true;}
        reg[i]=false;
    }
    fout<<len<<endl;
    if(cansee[n]&&cansee[n-1]){ //如果最后两个都合法,交换
        Line temp=line[n];
        line[n]=line[n-1];
        line[n-1]=temp;
    }
    for(int i=1;i<=n;i++) if(cansee[i])
        fout<<line[i].start.x<<' '<<line[i].start.y<<' '<<line[i].end.x<<' '<<line[i].end.y<<endl;
    return 0;
}