一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有N个角(顶点) (3 < N < 200)。 顶点不重合，它以逆时针方式以数组{xi, yi}给出(i=1,2,...,N)。
每一对相邻的顶点都是一条栅栏。因此共有N条栅栏 (定义xN+1=x1, yN+1=y1)。
这里有一个栅栏的例子和一个点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位的。
第3到N+2行: 每行一对整数(x,y)表示对应闭合栅栏的第k个顶点的坐标。坐标以逆时针顺序给出。整数绝对值不超过1000。
OUTPUT FORMAT:(file fence4.out)
如果给出的序列不是一个合法的闭合栅栏，那么输出文件只需要输出“NOFENCE”。
栅栏用两端的顶点表示，顶点的输出顺序以输入文件中的顺序为准。把栅栏按照最后一个点在输入文件中的顺序排序。如果两条栅栏的最后一个点是一样的，就以它们第一个点的顺序排序。
SAMPLE INPUT
13
5 5
0 0
7 0
5 2
7 5
5 7
3 5
4 9
1 8
2 5
0 9
-2 7
0 3
-3 1
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
解析：(转载)
比较复杂的计算几何，容易疏忽，且对数学功底要求较高。
首先判断多边形，主要是以下步骤：
枚举任意不相邻两条边
1.利用叉积做跨立试验，看是否规范相交。
2.出现叉积为0时立即判断点积的符号，如果点积<=0那么就是非规范相交。
3.如果1和2均不满足就是不相交。
当不存在不相邻的边相交时就可以肯定这是个闭合多边形。
然后就是寻找可以观察到的边。
这里提供一个比较方便的方法：
连接观察者与所有点顶点，延长（取很远一点）,然后将这些线绕观察者旋转一个很小的角度（0.0001即可）
旋转后的射线可以投射到的边就是可以观察到的。
对于第二问，我在这里给出一些数学推导：
(1)延长的计算公式：
A------------>B------------->C
已知A(x1,y1) B(x2,y2) 设C(x3,y3)
那么AB(x2-x1,y2-y1) AC(x3-x1,y3-y1)
因为AB与AC共线 故 (这里k我们定义成一个很大的常量)
x3-x1=k(x2-x1) => x3=k(x2-x1)+x1
y3-y1=k(y2-y1) => y3=k(y2-y1)+y1
(2)旋转后的坐标
设延长点的坐标为(a,b)，观察者的坐标为(x,y)
先将坐标系平移，使观察者在原点处，此时延长点坐标为(a-x,b-y)
设这个射线的长度为R那么 R*cos(x)=a-x R*sin(x)=b-y
旋转k度后设其坐标为(c,d)则
c=R*cos(x+k)=R*cos(x)*cos(k)-R*sin(x)*sin(k)=cos(k)(a-x)-sin(k)(b-y)
d=R*sin(x+k)=R*sin(x)*cos(k)+R*cos(x)*sin(k)=cos(k)(b-y)+sin(k)(a-x)将坐标系平移成原状：其旋转点坐标(A,B)为(cos(k)(a-x)-sin(k)(b-y)+x,cos(k)(b-y)+sin(k)(a-x)+y)
(3)关于截距
这里要说的就是，我们要判断旋转后的射线射到哪些边，就是对于每条射线要找到与该射线相交的边中截距最小的那条。因此我们必须用比较简单的方法算出解距。
我们这里用到共边定理：在四边形ABCD中，假定对角线AC与BD交于O
则BO:OD=S(ABC):S(ADC)
考虑到叉积的性质，这里可以转化为BO:OD=(ABxBC):(ADxDC)
(这里注意叉积的符号问题，如果出现比值为负要及时纠正顺序)
回到本题中，求射线的截距，我们将射线与边看成上面四边形的两条对角线(BD是射线B是观察者)。
然后先用两点间的距离公式求出射线的长度d，接着算出上述两个叉积k1,k2 (k1*k2>0)
那么这个截距BO=d*k1/(k1+k2)
【参考程序】：
/*
ID: XIONGNA1
PROG: fence4
LANG: C++
*/
#include<iostream>
#include<cmath>
#include<cstring>
#define k 1000
struct POINT
{
double x;
double y;
} v[1000],vv[1000];
struct EDGE
{
POINT a;
POINT b;
} e[1000];
int hash[1000]={0};
int n;
double x,y;
void read()
{
int i;
scanf("%d",&n); scanf("%lf%lf",&x,&y);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
e[1].a=v[1];e[1].b=v[n];
for(i=2;i<=n;i++)
{
e[i].a=v[i-1];
e[i].b=v[i];
}
}
double cp(double x1,double y1,double x2,double y2)
{
return x1*y2-x2*y1;
}
double dp(double x1,double y1,double x2,double y2)
{
return x1*x2+y1*y2;
}
int between(POINT a,EDGE b)
{
/*<-----.(a)-------> 点积<=0 在线上
>0 不在线上
返回值 0不在线上 1在顶点上 2在中间
*/
double x1,x2,y1,y2;
x1=a.x-b.a.x; y1=a.y-b.a.y;
x2=a.x-b.b.x; y2=a.y-b.b.y;
if(dp(x1,y1,x2,y2)>0) return 0;
if(dp(x1,y1,x2,y2)==0) return 1;
if(dp(x1,y1,x2,y2)<0) return 2;
}
int cross(EDGE a,EDGE b)
{
double x1,y1,x2,y2,x3,y3;
int flag1=0,flag2=0;
//相交类型: 0:不相交 1:规范相交 2:不规范相交
//跨立实验1： b.a -----\(a)-----b.b
x1=a.b.x-a.a.x; y1=a.b.y-a.a.y;//向量 a .b---->a.a
x2=b.a.x-a.a.x; y2=b.a.y-a.a.y;//跨立向量b.a-->a.a
x3=b.b.x-a.a.x; y3=b.b.y-a.a.y;//跨立向量b.b-->a.a
if(cp(x3,y3,x1,y1)*cp(x2,y2,x1,y1)<0) flag1=1;
else
{
if(cp(x3,y3,x1,y1)==0)
if(between(b.b,a)) return 2;
if(cp(x2,y2,x1,y1)==0)
if(between(b.a,a)) return 2;
}
//跨立实验2： a.a -----\(b)-----a.b
x1=b.b.x-b.a.x; y1=b.b.y-b.a.y;//向量 b.b---->b.a
x2=a.a.x-b.a.x; y2=a.a.y-b.a.y;//跨立向量a.a-->b.a
x3=a.b.x-b.a.x; y3=a.b.y-b.a.y;//跨立向量a.b-->b.a
if(cp(x3,y3,x1,y1)*cp(x2,y2,x1,y1)<0) flag2=1;
else
{
if(cp(x3,y3,x1,y1)==0)
if(between(a.b,b)) return 2;
if(cp(x2,y2,x1,y1)==0)
if(between(a.a,b)) return 2;
}
if(flag1&&flag2) return 1;
return 0;
}
int isnext(int a,int b)
{
if(a==1&&b==n) return 1;
if(b==1&&a==n) return 1;
if(a+1==b||b+1==a) return 1;
if(a==b) return 1;
return 0;
}
void check()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(isnext(i,j)) continue;
if(cross(e[i],e[j]))
{
printf("NOFENCE\n");
exit(0);
}
}
}
double dis(POINT a,EDGE b)
{
double x1,y1,x2,y2,x3,y3,x4,y4;
double d;
double k1,k2;
x1=b.a.x-x; y1=b.a.y-y;
x2=b.b.x-x; y2=b.b.y-y;
x3=b.a.x-a.x; y3=b.a.y-a.y;
x4=b.b.x-a.x; y4=b.b.y-a.y;
k1=cp(x1,y1,x2,y2); k2=cp(x4,y4,x3,y3);
d=sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));
d=d*(k1/(k1+k2));
return d;
}
void ray()//主要算法流程：投影--〉旋转--〉取最小截距
{
int i,j,op;
double min=99999999;
double c,s;
c=cos(0.0001);s=sin(0.0001);
EDGE temp;
for(i=1;i<=n;i++)
{
vv[i].x=k*(v[i].x-x)+x;vv[i].y=k*(v[i].y-y)+y;
vv[i].x=c*(vv[i].x-x)-s*(vv[i].y-y)+x;
vv[i].y=c*(vv[i].y-y)+s*(vv[i].x-x)+y;
}//投影且旋转
for(i=1;i<=n;i++)
{
min=99999999;
op=0;
temp.a.x=x; temp.a.y=y; temp.b=vv[i];
for(j=1;j<=n;j++)
{
if(cross(temp,e[j])==1)
if(dis(vv[i],e[j])<min)
{
op=j;
min=dis(vv[i],e[j]);
}
}
hash[op]=1;
}
}
void print()
{
int i,sum=0;
for(i=1;i<=n;i++)
{
if(hash[i]) sum++;
}
printf("%d\n",sum);
for(i=2;i<n;i++)
if(hash[i])
printf("%.lf %.lf %.lf %.lf\n",e[i].a.x,e[i].a.y,e[i].b.x,e[i].b.y);
if(hash[1])
printf("%.lf %.lf %.lf %.lf\n",e[1].a.x,e[1].a.y,e[1].b.x,e[1].b.y);
if(hash[i])
printf("%.lf %.lf %.lf %.lf\n",e[i].a.x,e[i].a.y,e[i].b.x,e[i].b.y);
}
int main()
{
freopen("fence4.in","r",stdin);
freopen("fence4.out","w",stdout);
read();
check();
ray();
print();
return 0;
}