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;     
}