USACO Section 3.4 Closed Fences - 暴力枚举..

     好恶心的题...断断续续作了三天才做出来...想吐了...试了N多方法..重写了N遍代码...终于让我给过了..

     第一问很好做...只要判断下有没有两直线相交就行了..做两次差乘判断...

     第二问我AC的思路是将每个线段给暴力离散化..离散为500个点..然后将每个点与视野点(x,y)做线段...若是有一个点做成的线段中间没有被其他线段所截断..那么就可判定所离散的线段是能够第一眼看到的..

     首先我这个方法不够严谨...因为离散化这种方法本来就存在的细微的出错概率..离散得越细出错概率就越小...还有我的方法似乎一直没有考虑线段与视野点三点共线的情况...呃..弱爆了...不过AC了就好~~

Program:

/*
ID: zzyzzy12
LANG: C++
TASK: fence4
*/
#include<iostream>
#include<istream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<algorithm>
#include<queue>
#define oo 1000000000
#define ll long long
#define pi (atan(2)+atan(0.5))*2
using namespace std;
int n;
double x,y;
struct node1
{
double x,y;
}a[205];
struct node2
{
double x1,y1,x2,y2;
}line[205];
bool cross(node2 a,node2 b,int mode)
{
double x1,y1,x2,y2,s1,s2,p1,p2;
x1=a.x1-b.x1; y1=a.y1-b.y1; x2=b.x2-b.x1; y2=b.y2-b.y1;
s1=x1*y2-x2*y1;
x1=a.x2-b.x1; y1=a.y2-b.y1;
s2=x1*y2-x2*y1;
p1=s1*s2;
x1=b.x1-a.x1; y1=b.y1-a.y1; x2=a.x2-a.x1; y2=a.y2-a.y1;
s1=x1*y2-x2*y1;
x1=b.x2-a.x1; y1=b.y2-a.y1;
s2=x1*y2-x2*y1;
p2=s1*s2;
if (!mode && p1<-0.000001 && p2<-0.000001) return true;
if (mode && p1<0.000001 && p2<0.000001) return true;
return false;
}
double abs_b(double x)
{
if (x<0) return -x;
return x;
}
void getanswer()
{
int i,j,t,num=0;
double len,k,min_x,max_x,max_y,min_y;
line[1].x1=a[1].x; line[1].y1=a[1].y; line[1].x2=a[n].x; line[1].y2=a[n].y;
bool can[205];
for (i=1;i<=n;i++)
{
line[i].x1=a[i].x; line[i].y1=a[i].y; line[i].x2=a[i+1].x; line[i].y2=a[i+1].y;
for (j=1;j<i;j++)
if (cross(line[i],line[j],0))
{
printf("NOFENCE\n");
return;
}
}
line[n]=line[n-1]; line[n-1].x1=a[1].x; line[n-1].y1=a[1].y; line[n-1].x2=a[n].x; line[n-1].y2=a[n].y;
memset(can,false,sizeof(can));
line[0].x1=x; line[0].y1=y;
for (i=1;i<=n;i++)
{
min_x=min(line[i].x1,line[i].x2); max_x=max(line[i].x1,line[i].x2);
min_y=min(line[i].y1,line[i].y2); max_y=max(line[i].y1,line[i].y2);
if (abs_b(max_x-min_x)>0.01)
{
len=(max_x-min_x)/500;
for (k=min_x;k<=max_x;k+=len)
{
line[0].x2=k; line[0].y2=(k-line[i].x1)*(line[i].y2-line[i].y1)/(line[i].x2-line[i].x1)+line[i].y1;
for (j=1;j<=n;j++)
if (j!=i && cross(line[j],line[0],1))
goto A;
if (!can[i]) num++;
can[i]=true;
A: ;
if (can[i]) goto C;
}
}else
{
len=(max_y-min_y)/500;
for (k=min_y;k<=max_y;k+=len)
{
line[0].y2=k; line[0].x2=(k-line[i].y1)*(line[i].x2-line[i].x1)/(line[i].y2-line[i].y1)+line[i].x1;
for (j=1;j<=n;j++)
if (j!=i && cross(line[j],line[0],1))
goto B;
if (!can[i]) num++;
can[i]=true;
B: ;
if (can[i]) goto C;
}
}
C: ;
}
printf("%d\n",num);
for (i=1;i<=n;i++)
if (can[i]) printf("%.0lf %.0lf %.0lf %.0lf\n",line[i].x1,line[i].y1,line[i].x2,line[i].y2);
}
int main()
{
freopen("fence4.in","r",stdin);
freopen("fence4.out","w",stdout);
scanf("%d%lf%lf",&n,&x,&y);
for (int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
a[0]=a[n]; a[n+1]=a[1];
getanswer();
return 0;
}