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

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

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

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

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

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

Program:

/* ID: zzyzzy12 LANG: C++ TASK: fence4*/ #include #include #include #include #include #include #include #include #define oo 1000000000 #define ll long long #define pi (atan(2)+atan(0.5))*2using 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;j0.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; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。