|
Posted on 2010-09-19 01:45 Uriel 阅读(422) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 计算几何
这几天做计算几何一直不顺,各种WA。。这题做了一天多。。WA到哭了。。 这题思路很简单,用平面图的欧拉定理,V+F-E=2;其中V是顶点数,F是分割出的面数,E是边数。 方法是:先两重for求出所有的交点,然后判每个点在几条线段上,每一个交点将几条线段多分开一段。这里纠结了很久,各种WA。。无奈换思路,求出所有交点之后用set存,顺便判重,然后枚举n-1跳条线段,看每条线段上有几个交点,但是因为线段两端的点不会分割线段,所以要剪掉。。这里又是各种WA。。今天一晚上都杯具在这里。。然后自认为解决了这个问题之后依然WA。。无奈找到某解题报告上的数据,竟然有重点,重边。。无奈了。。各种判重,各种eps之后还是WA。。无奈找到另一份解题报告,发现跟我的不同之处是最后对端点的处理,判是不是一条线段的开始点,不是的话边数就++,但是没有判重点,重边。。也能AC。。我改了判端点之后重点,重边的sampl也能过。。然后总算AC了。。不过比解题报告慢很多。。set导致的。。 但是我的重载<跟解题报告不同,我直接!= , < 这么比的话Discuss某sample过不了,于是又加了eps才过,话说还是第一次这么写比较函数。。= =。。弱啊。。 贴上丑陋的代码一份,有错误欢迎大家指正
//Problem: 2284 User: Uriel //Memory: 944K Time: 1344MS //Language: C++ Result: Accepted
#include<set> #include<math.h> #include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; #define eps 1e-10 #define zero(x) (((x)>0?(x):-(x))<eps)
struct point{ double x,y; }p[100000];
struct line{ point a,b; }l[100000];
bool operator<(point a,point b){ if(fabs(a.x-b.x)>eps)return a.x-b.x<-eps; return a.y-b.y<-eps; }
int n,E;
double xmult(point p1,point p2,point p0){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); }
int dots_inline(point p1,point p2,point p3){ return zero(xmult(p1,p2,p3)); }
int dot_online_in(point p,point l1,point l2){ return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps; }
int same_side(point p1,point p2,point l1,point l2){ return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps; }
int intersect_in(point u1,point u2,point v1,point v2){ if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2)) return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2); return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2); }
point intersection(point u1,point u2,point v1,point v2){ point ret=u1; double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x)); ret.x+=(u2.x-u1.x)*t; ret.y+=(u2.y-u1.y)*t; return ret; }
double len(line a){ return sqrt((a.a.x-a.b.x)*(a.a.x-a.b.x)+(a.a.y-a.b.y)*(a.a.y-a.b.y)); }
bool ok(int x){ if(len(l[x])<eps)return false; if(fabs(l[x].a.x-l[x-1].a.x)<eps && fabs(l[x].b.x-l[x-1].b.x)<eps && fabs(l[x].a.y-l[x-1].a.y)<eps && fabs(l[x].b.y-l[x-1].b.y)<eps)return false; return true; }
int main(){ int i,j; int cse=1; while(scanf("%d",&n),n){ for(i=0;i<n;i++)scanf("%lf %lf",&p[i].x,&p[i].y); set<point> st; E=0; set<point>::iterator it; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==j)continue; if(intersect_in(p[i],p[(i+1)%n],p[j],p[(j+1)%n])){ // it=st.find(intersection(p[i],p[(i+1)%n],p[j],p[(j+1)%n])); // if(it==st.end())st.insert(intersection(p[i],p[(i+1)%n],p[j],p[(j+1)%n])); st.insert(intersection(p[i],p[(i+1)%n],p[j],p[(j+1)%n])); } } } for(i=0;i<n;i++){ for(it=st.begin();it!=st.end();it++){ if(dot_online_in(*it,p[i],p[(i+1)%n]) && !(fabs(it->x-p[i].x)<eps && fabs(it->y-p[i].y)<eps))E++; } } if(E>1)printf("Case %d: There are %d pieces.\n",cse++,E+2-st.size()); else printf("Case %d: There are 1 pieces.\n",cse++); } return 0; }
|