|
|
Posted on 2010-09-19 01:45 Uriel 阅读(429) 评论(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;
}
|