/**//* 题意:问给定的n条线把平面分出了几个有限的区域 O(n^2lg(n)) 首先处理出所有交点,并给所有点标号,注意合并相同的点。 map<Point,int> vector<Point> 然后给直接相连的两点之间连两条有向边,处理成邻接表。 atan2(y,x)得到与x轴的角(极角) 注意只连相邻点!!!!!!!!!!!!!! 显然至多有O(n^2)个点和O(n^2)条边。 最后算法的核心就是枚举所有边作为起始边,“走”出所有的区域。 “走”的算法是这样的,每走到一个顶点,就找从这个点出发相对当前边的方向最“左”的边。 -- 这样保证形成的凸多边形是最小的,最左边,那么面积直接叉积累加即可 这样子走,环的边只会走一次!!!
如果最后回到了最初枚举的起点就找到了一个有限区域。 如果这条边不在当前边的方向的“左”边说明这不是一个有限区域。否则更新当前边继续找。 对于“走”过的边标上标记,则以后遇到可以不再继续搜下去。 而在找从一个点出发相对当前边的方向最“左”的边的时候可以先对所有边按极角排序再二分查找。 其实这个找的过程在纸上模拟还是非常简单的,不过变成代码就可能有各种bug了……
对每条边,朝最左边的边走,这样逆时针走,叉积面积累加即可 而且,走过的边只会走一次,不用再走 这一次要么成环,要么不是环
跟zoj 1030 类似 往最左/右走 就走出一个最小的环 */ #include<cstdio> #include<vector> #include<map> #include<cmath> #include<algorithm>
using namespace std;
const double eps = 1e-15; const double PI = acos(-1.0); const int MAXN = 81;
struct Point { double x,y; //map 需要定义 < 、== bool operator<(const Point &B)const { if(fabs(x-B.x)<eps)return y<B.y; return x<B.x; } bool operator==(const Point &B)const { return fabs(x-B.x)<eps&&fabs(y-B.y)<eps; } }; struct Line { Point a,b; }; bool parallel(const Line &la,const Line &lb) { return fabs((la.a.x-la.b.x)*(lb.a.y-lb.b.y)-(lb.a.x-lb.b.x)*(la.a.y-la.b.y))<eps; } Point intersection(const Line &la,const Line &lb) { Point ret = la.a; double r = ((la.a.x-lb.a.x)*(lb.a.y-lb.b.y)-(la.a.y-lb.a.y)*(lb.a.x-lb.b.x))/ ((la.a.x-la.b.x)*(lb.a.y-lb.b.y)-(la.a.y-la.b.y)*(lb.a.x-lb.b.x)); ret.x += (la.b.x-la.a.x)*r; ret.y += (la.b.y-la.a.y)*r; return ret; } struct Edge { double w; int v; bool vi; Edge(int v,double w):v(v),w(w),vi(false){} bool operator<(const Edge &B)const//按照极角排序 { return w<B.w; } };
map<Point,int>mp; vector<Point>vp,p[MAXN]; Line lines[MAXN]; vector<Edge>E[MAXN*MAXN/2];//n*n/2 vector<double> ans;
bool ok(double a,double b)//判断b是否在a的左边 { if(b>a+eps)return b+eps<a+PI; return b+eps<a-PI; } int search(vector<Edge>&E,double w)//找到w反边的 { double d = w + PI; if(d>PI+eps)d-=2*PI; int id; for(id=0;id<E.size();id++)//w反边的前一个 注意角看成循环的 所以有可能E.size()-1 if(fabs(E[id].w-d)<eps) { if(id)id--; else id=E.size()-1; break; } //judge again whether id is in the left? return ok(E[id].w,d)?id:-1; } int main() { int T; for(scanf("%d",&T);T--;T?puts(""):0) { int N; scanf("%d",&N); mp.clear(); vp.clear(); for(int i=0;i<N;i++) { scanf("%lf%lf%lf%lf",&lines[i].a.x,&lines[i].a.y,&lines[i].b.x,&lines[i].b.y); p[i].clear(); for(int j=0;j<i;j++) { if(parallel(lines[i],lines[j]))continue; Point pt = intersection(lines[i],lines[j]); mp[pt];// p[i].push_back(pt); p[j].push_back(pt); } } //mp用来处理重复,然后编号 vp存点 int m=0; for(map<Point,int>::iterator it = mp.begin();it!=mp.end();it++) { vp.push_back(it->first); it->second = m; E[m++].clear(); } //相邻点连边 for(int i=0;i<N;i++) { if(p[i].size()<2)continue; sort(p[i].begin(),p[i].end()); p[i].erase(unique(p[i].begin(),p[i].end()),p[i].end());//unique double ab = atan2(p[i].back().y-p[i].front().y,p[i].back().x-p[i].front().x); double ba = atan2(p[i].front().y-p[i].back().y,p[i].front().x-p[i].back().x); for(int j=1;j<p[i].size();j++)//建边 注意只连相邻点!!!!!!!!!!!!!! { int a = mp[p[i][j-1]],b=mp[p[i][j]]; E[a].push_back(Edge(b,ab)); E[b].push_back(Edge(a,ba)); } } //对每个点的相连的边按极角排序 for(int i=0;i<m;i++) sort(E[i].begin(),E[i].end()); ans.clear(); //enum for(int i=0;i<m;i++)//枚举每条边作为起始边,vi过的就continue for(int j=0;j<E[i].size();j++) { if(E[i][j].vi)continue; int a=i,b=j,c; //按照逆时针,面积直接叉积累加即可 double S = vp[a].x*vp[E[i][j].v].y-vp[a].y*vp[E[i][j].v].x; E[i][j].vi=true; while(E[a][b].v!=i) { //找最左边的,这样形成的凸多边形才最小 //如果相切的,相当于有2条边,正反的,vi不会影响到反边 c = search(E[E[a][b].v],E[a][b].w); if(c==-1) { S=0;break; } a=E[a][b].v,b=c; if(E[a][b].vi)//该边已vi过,所以不能用了,就S = 0 { S=0;break; } E[a][b].vi=true; S += vp[a].x*vp[E[a][b].v].y-vp[a].y*vp[E[a][b].v].x; } if(S>2*eps)ans.push_back(S);//S/2>eps }
printf("%d\n",ans.size()); sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) printf("%.4f\n",ans[i]/2);//叉积/2 } return 0; }
跟zoj 1030 类似 往最左/右走 就走出一个最小的环
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|