 /**//*
题意:问给定的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
搜索
最新评论

|
|