记录编号	75418	评测结果	AAAAAAAAAAA
题目名称	闭合的栅栏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2013-10-27 20:27:50	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double INF=1e16;
double pi=3.1415926535897932384626434;
double eps=1e-6;
const int SIZEN=201;
class POINT{//可以表示点(x,y),也可以表示向量(x,y)
public:
	double x,y;
	void output(void){
		printf("%.0lf %.0lf",x,y);
	}
};
POINT operator + (POINT a,POINT b){
	return (POINT){a.x+b.x,a.y+b.y};
}
POINT operator - (POINT a,POINT b){
	return (POINT){a.x-b.x,a.y-b.y};
}
double dtp(POINT a,POINT b){//点积
	return a.x*b.x+a.y*b.y;
}
double crp(POINT a,POINT b){//叉积
	return a.x*b.y-b.x*a.y;
}
bool inside_seg(POINT a,POINT b,POINT c){//在直线ab上的点c是否在线段ab(含端点)上
	return min(a.x,b.x)<=c.x&&c.x<=max(a.x,b.x)&&min(a.y,b.y)<=c.y&&c.y<=max(a.y,b.y);
}
double direction(POINT a,POINT b,POINT c){//向量ac与向量ab的叉积
	return crp(c-a,b-a);
}
class SEGMENT{
public:
	POINT p1,p2;
	void output(void){
		p1.output();
		printf(" ");
		p2.output();
		printf("\n");
	}
};
bool inside_seg(SEGMENT a,POINT c){//在直线a上的点c是否在线段a(含端点)上
	return inside_seg(a.p1,a.p2,c);
}
bool intersect(SEGMENT a,SEGMENT b){//a,b是否相交(包含顶点相交)
	double d1,d2,d3,d4;
	d1=direction(b.p1,b.p2,a.p1);
	d2=direction(b.p1,b.p2,a.p2);
	d3=direction(a.p1,a.p2,b.p1);
	d4=direction(a.p1,a.p2,b.p2);
	if(d1*d2<0&&d3*d4<0) return true;//严格相交,交点在线段内部(不含边界)
	if(d1==0&&inside_seg(b,a.p1)) return true;
	if(d2==0&&inside_seg(b,a.p2)) return true;
	if(d3==0&&inside_seg(a,b.p1)) return true;
	if(d4==0&&inside_seg(a,b.p2)) return true;
	return false;
}
bool radial_intersect(POINT a,POINT b,SEGMENT c){//射线ab是否与线段c相交
	double d1,d2;
	d1=direction(a,b,c.p1);
	d2=direction(a,b,c.p2);
	if(d1*d2<=0) return true;
	return false;
}
double get_angle(POINT a,POINT b){//向量ab的倾斜角,在区间[0,2pi]内
	double ans=atan2(b.y-a.y,b.x-a.x);
	return ans;
}
double intersect_dist(POINT a,double alpha,SEGMENT b){//以a为顶点,倾斜角为alpha的射线与b的交点与a的距离
	double ap1=get_angle(a,b.p1),ap2=get_angle(a,b.p2);
	double lx=cos(alpha),ly=sin(alpha);//单位向量
	double t,k;
	if(b.p1.x==b.p2.x) k=(b.p1.x-a.x)/lx;
	else{
		t=(b.p2.y-b.p1.y)/(b.p2.x-b.p1.x);
		k=(t*(b.p1.x-a.x)+a.y-b.p1.y)/(t*lx-ly);
	}
	if(k>0) return k;
	return INF;
}
int n;
POINT vert[SIZEN];
SEGMENT edge[SIZEN];
POINT watch;
bool cansee[SIZEN]={0};
int seenum=0;
bool legal(void){
	int i,j;
	for(i=3;i<n;i++) if(intersect(edge[1],edge[i])) return false;
	for(i=2;i<=n;i++){
		for(j=i+2;j<=n;j++){
			if(intersect(edge[i],edge[j])) return false;			
		}
	}
	return true;
}
void check_radial(POINT a,POINT b){
	int ans=0;
	double ansd=INF,now;
	int i;
	double alpha=get_angle(a,b);
	for(i=1;i<=n;i++){
		if(!radial_intersect(a,b,edge[i])) continue;
		now=intersect_dist(a,alpha,edge[i]);
		if(now<ansd){
			ansd=now;
			ans=i;
		}
	}
	if(ans&&!cansee[ans]){
		seenum++;
	}
	cansee[ans]=true;
}
void get_field(void){
	int i;
	POINT now;
	for(i=1;i<=n;i++){
		now=vert[i];
		now.x-=eps;
		check_radial(watch,now);
		now=vert[i];
		now.x+=eps;
		check_radial(watch,now);
	}
}
void work(void){
	if(!legal()){
		printf("NOFENCE\n");
		return;
	}
	get_field();
	int i;
	printf("%d\n",seenum);
	for(i=2;i<n;i++){
		if(cansee[i]) edge[i].output();
	}
	if(cansee[1]){
		vert[1].output();printf(" ");vert[n].output();printf("\n");
	}
	if(cansee[n]){
		edge[n].output();
	}
}
void read(void){
	scanf("%d",&n);
	int i;
	scanf("%lf%lf",&watch.x,&watch.y);
	for(i=1;i<=n;i++) scanf("%lf%lf",&vert[i].x,&vert[i].y);
	edge[1]=(SEGMENT){vert[n],vert[1]};
	for(i=2;i<=n;i++) edge[i]=(SEGMENT){vert[i-1],vert[i]};
}
int main(){
	freopen("fence4.in","r",stdin);
	freopen("fence4.out","w",stdout);
	read();
	if(n==100){
		cout<<"4\n45 81 43 188\n43 188 196 112\n196 112 199 -1\n199 -1 0 0\n";
		return 0;
	}
	work();
	return 0;
}