这题水的真不易。。300多行 累死了 对着数据查错啊
枚举每个边上的点到源点 是否中间隔着别的边 每条边划分500份就够了 注意一下与源点在一条直线上的边不算
几何 啊，，好繁琐 参考各种模版。。
/*
ID: shangca2
LANG: C++
TASK: fence4
*/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
typedef struct pointt
{
double x,y;
pointt(double x=,double y=):x(x),y(y){}
}vec;
struct node
{
int x1,y1,x2,y2,o1,o2;
}po[];
vec p,pp[],q[];
int e,n;
vec operator + (vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator - (pointt a,pointt b){return vec(a.x-b.x,a.y-b.y);}
vec operator * (vec a,double b){return vec(a.x*b,a.y*b);}
vec operator / (vec a,double b){return vec(a.x/b,a.y/b);}
bool operator < (const pointt &a,const pointt &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps = 1e-;
int dcmp(double x)
{
if(fabs(x)<eps) return ;
else return x<?-:;
}
bool operator == (const pointt &a,const pointt &b)
{
return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
}
double dot(vec a,vec b)
{
return a.x*b.x+a.y*b.y;
}
double cross(vec a,vec b)
{
return a.x*b.y-a.y*b.x;
}
bool segprointer(pointt a1,pointt a2,pointt b1,pointt b2)
{
double c1 = cross(a2-a1,b1-a1),c2 = cross(a2-a1,b2-a1),
c3 = cross(b2-b1,a1-b1),c4 = cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<&&dcmp(c3)*dcmp(c4)<;
}
bool cmp(node a,node b)
{
if(a.o2==b.o2)
return a.o1<b.o1;
return a.o2<b.o2;
}
int judge(int i,int j)
{
int g; for(g = ; g <= n ; g++)
{
if(g==i)
continue;
if(segprointer(q[j],p,pp[g],pp[g+]))
break;
}
if(g==n+)
{
e++;
if(i==n)
{
po[e].x1 = pp[i+].x;
po[e].y1 = pp[i+].y;
po[e].x2 = pp[i].x;
po[e].y2 = pp[i].y;
po[e].o1 = ;
po[e].o2 = i;
}
else
{
po[e].o1 = i;
po[e].o2 = i+;
po[e].x1 = pp[i].x;
po[e].y1 = pp[i].y;
po[e].x2 = pp[i+].x;
po[e].y2 = pp[i+].y;
}
return ;
}
return ;
}
double xmult(vec p1,vec p2,vec p3)
{
return (p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y);
}
int dots(vec p1,vec p2,vec p3)
{
return dcmp(xmult(p1,p2,p3));
}
int main()
{
freopen("fence4.in","r",stdin);
freopen("fence4.out","w",stdout);
int i,j,o,g;
cin>>n;
cin>>p.x>>p.y;
for(i = ;i <= n ; i++)
cin>>pp[i].x>>pp[i].y;
pp[n+] = pp[];
for(i = ; i <= n ; i++)
{
for(j = ; j <= i- ; j++)
{
if(i==n&&j==)
continue;
if(segprointer(pp[i],pp[i+],pp[j],pp[j+]))
{
puts("NOFENCE");
return ;
}
}
}
vec no;
for(i = ; i <= n ; i++)
{
if(!dots(p,pp[i],pp[i+]))
continue;
o = ;
int fo=;
if(pp[i+].x==pp[i].x)
{
double x1 = pp[i].x;
double y1;
if(pp[i].y<pp[i+].y)
{
double xx = (pp[i+].y-pp[i].y)/300.0;
y1 = pp[i].y+xx;
while(y1<pp[i+].y)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
y1+=xx;
}
}
else
{
double xx = (pp[i].y-pp[i+].y)/300.0;
y1 = pp[i].y-xx;
while(y1>pp[i+].y)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
y1-=xx;
}
}
}
else if(pp[i+].y==pp[i].y)
{ double x1;
double y1=pp[i].y;
if(pp[i+].x>pp[i].x)
{
double xx = (pp[i+].x-pp[i].x)/500.0;
x1 = pp[i].x+xx;
while(x1<pp[i+].x)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
x1+=xx;
}
}
else
{
double xx = (pp[i].x-pp[i+].x)/500.0;
x1 = pp[i].x-xx;
while(x1>pp[i+].x)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
if(i==)
cout<<x1<<" "<<y1<<endl;
break;
}
x1-=xx;
}
}
}
else
{
double d = (pp[i+].y-pp[i].y)/(pp[i+].x-pp[i].x);
double k1,x1,y1;
double xx = fabs((pp[i+].x-pp[i].x)/500.0);
k1 = 1.0*fabs(d);
if(pp[i+].x>pp[i].x&&pp[i+].y>pp[i].y)
{
x1 = pp[i].x+0.1;
y1 = pp[i].y+0.1*k1;
while(x1<pp[i+].x&&y1<pp[i+].y)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
x1+=xx;
y1+=xx*k1;
}
}
else if(pp[i+].x<pp[i].x&&pp[i+].y>pp[i].y)
{
x1 = pp[i].x-0.1;
y1 = pp[i].y+0.1*k1;
while(x1>pp[i+].x&&y1<pp[i+].y)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
x1-=xx;
y1+=xx*k1;
}
}
else if(pp[i+].x<pp[i].x&&pp[i+].y<pp[i].y)
{
x1 = pp[i].x-0.1;
y1 = pp[i].y-0.1*k1;
while(x1>pp[i+].x&&y1>pp[i+].y)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
x1-=xx;
y1-=xx*k1;
}
}
else
{
x1 = pp[i].x+0.1;
y1 = pp[i].y-0.1*k1;
while(x1<pp[i+].x&&y1>pp[i+].y)
{
o++;
q[o].x = x1;
q[o].y = y1;
if(judge(i,o))
{
fo = ;
break;
}
x1+=xx;
y1-=xx*k1;
}
}
}
}
sort(po+,po+e+,cmp);
cout<<e<<endl;
for(i = ; i <= e ; i++)
{
cout<<po[i].x1<<" "<<po[i].y1<<" "<<po[i].x2<<" "<<po[i].y2<<endl;
}
return ;
}