|
|
Posted on 2010-09-17 17:59 Uriel 閱讀(412) 評論(0) 編輯 收藏 引用 所屬分類: POJ 、 計(jì)算幾何
5門專業(yè)必修+4門大類選修真糾結(jié)。。微機(jī)、計(jì)算機(jī)圖像處理還行，數(shù)據(jù)庫也還行，計(jì)算機(jī)組成原理算得頭大，最糾結(jié)的還是編譯原理，K老師的課漏聽30min肯定就聽不懂了，作業(yè)又一堆。。每天白天都用來上課+寫作業(yè)了。。就晚上選修課結(jié)束回1教切會題。。 看起來很水的一道計(jì)算幾何卡了兩天才過。。悲劇啊。。 一開始沒注意相似的點(diǎn)是對應(yīng)的，不會說第一個多邊形的第1個點(diǎn)對應(yīng)第二個多邊形的第3個點(diǎn)之類的，想了幾個WS算法，WA。。今天注意到了這點(diǎn)，結(jié)果改來改去還是不對。。最后看了某解題報(bào)告，把判轉(zhuǎn)向那里改了一下，總算過了。。 代碼比較挫。。很多無用的東西懶得擦掉了。。
 #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;
}
|