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 1931 Biometrics---计算几何

Posted on 2010-09-17 17:59 Uriel 阅读(397) 评论(0)  编辑 收藏 引用 所属分类: POJ计算几何
        5门专业必修+4门大类选修真纠结。。微机、计算机图像处理还行,数据库也还行,计算机组成原理算得头大,最纠结的还是编译原理,K老师的课漏听30min肯定就听不懂了,作业又一堆。。每天白天都用来上课+写作业了。。就晚上选修课结束回1教切会题。。

        看起来很水的一道计算几何卡了两天才过。。悲剧啊。。

        一开始没注意相似的点是对应的,不会说第一个多边形的第1个点对应第二个多边形的第3个点之类的,想了几个WS算法,WA。。今天注意到了这点,结果改来改去还是不对。。最后看了某解题报告,把判转向那里改了一下,总算过了。。

        代码比较挫。。很多无用的东西懒得擦掉了。。

#include<math.h>
#include
<stdio.h>
#include
<stdlib.h>
#include
<algorithm>
using namespace std;
#define eps 1e-6
const double INF=1e20;

struct point{
    
double x,y;
    point 
operator-(point &b){
        point c;
        c.x 
= x - b.x;
        c.y 
= y - b.y;
        
return c;
    }

}
p1[11],p2[11];

int n;
int dir1[11],dir2[11];
double len1[11],len2[11];

double dis(point a,point b){
    
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}


double Cos(point p0,point p1,point p2){
    
return (dis(p0,p1)+dis(p1,p2)-dis(p0,p2))/(2*sqrt(dis(p0,p1))*sqrt(dis(p1,p2)));
}


int cross_product(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}


double dot_product(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}


double cross(point a, point b){
    
return a.x * b.y - a.y * b.x;
}


int get_dir(point p1,point p2,point p3){
    
double t1=cross(p2-p1,p3-p2);
    
if(fabs(t1)<eps)return 1;
    
if(t1<0)return 2;
    
else return 3;    
}


int main(){
    
int f1,f2,i,j,cnt;
    
bool ok;
    
double minn1,len,minn2,cons;
    
while(scanf("%d",&n),n){
        
for(i=0;i<n;i++)scanf("%lf %lf",&p1[i].x,&p1[i].y);
        
for(i=0;i<n;i++)scanf("%lf %lf",&p2[i].x,&p2[i].y);
        cons
=sqrt(dis(p1[0],p1[1]))/sqrt(dis(p2[0],p2[1]));
        
for(i=0;i<n;i++){
            len1[i]
=sqrt(dis(p1[i],p1[(i+1)%n]))/cons;
            len2[i]
=sqrt(dis(p2[i],p2[(i+1)%n]));
        }

        ok
=true;
        
for(i=0;i<n;i++){
            
if(fabs(len1[i]-len2[i])>eps){
                ok
=false;
                
break;
            }

        }

        
if(ok){
            
for(i=0;i<n;i++){
                
if(fabs(fabs(Cos(p1[i],p1[(i+1)%n],p1[(i+2)%n]))-fabs(Cos(p2[i],p2[(i+1)%n],p2[(i+2)%n])))>eps){
                    ok
=false;
                    
break;
                }

            }

        }

        
if(ok){
            
for(i=0;i<n;i++){
                
if(get_dir(p1[i],p1[(i+1)%n],p1[(i+2)%n])!=get_dir(p2[i],p2[(i+1)%n],p2[(i+2)%n])){
                    ok
=false;
                    
break;
                }

            }

        }

        
if(ok)puts("similar");
        
else
            puts(
"dissimilar");
    }

    
return 0;
}


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