|
|
Posted on 2010-09-19 01:45 Uriel 閱讀(433) 評(píng)論(0) 編輯 收藏 引用 所屬分類: POJ 、 計(jì)算幾何
這幾天做計(jì)算幾何一直不順，各種WA。。這題做了一天多。。WA到哭了。。 這題思路很簡(jiǎn)單，用平面圖的歐拉定理，V+F-E=2；其中V是頂點(diǎn)數(shù)，F(xiàn)是分割出的面數(shù)，E是邊數(shù)。 方法是：先兩重for求出所有的交點(diǎn)，然后判每個(gè)點(diǎn)在幾條線段上，每一個(gè)交點(diǎn)將幾條線段多分開一段。這里糾結(jié)了很久，各種WA。。無奈換思路，求出所有交點(diǎn)之后用set存，順便判重，然后枚舉n-1跳條線段，看每條線段上有幾個(gè)交點(diǎn)，但是因?yàn)榫€段兩端的點(diǎn)不會(huì)分割線段，所以要剪掉。。這里又是各種WA。。今天一晚上都杯具在這里。。然后自認(rèn)為解決了這個(gè)問題之后依然WA。。無奈找到某解題報(bào)告上的數(shù)據(jù)，竟然有重點(diǎn)，重邊。。無奈了。。各種判重，各種eps之后還是WA。。無奈找到另一份解題報(bào)告，發(fā)現(xiàn)跟我的不同之處是最后對(duì)端點(diǎn)的處理，判是不是一條線段的開始點(diǎn)，不是的話邊數(shù)就++，但是沒有判重點(diǎn)，重邊。。也能AC。。我改了判端點(diǎn)之后重點(diǎn)，重邊的sampl也能過。。然后總算AC了。。不過比解題報(bào)告慢很多。。set導(dǎo)致的。。 但是我的重載<跟解題報(bào)告不同，我直接!= , < 這么比的話Discuss某sample過不了，于是又加了eps才過，話說還是第一次這么寫比較函數(shù)。。= =。。弱啊。。 貼上丑陋的代碼一份，有錯(cuò)誤歡迎大家指正
 //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;
}
|