|
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
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#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)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct point {
double x,y;
}p[100000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct line {
point a,b;
}l[100000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,E;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dots_inline(point p1,point p2,point p3) {
return zero(xmult(p1,p2,p3));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int same_side(point p1,point p2,point l1,point l2) {
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i,j;
int cse=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=0;i<n;i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(j=0;j<n;j++) {
if(i==j)continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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]));
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=0;i<n;i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
|