Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 2284 That Nice Euler Circuit---计算几何

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理