来自LRJ
类似卷包裹算法
把每条边拆成两条半边(有向边)，u->v和v->u，并且只取每条有向边的左边的区域
思路就是从每个点出发(包括新产生的交点)，沿着逆时针转的最多的一条边作为下一条边，直到回到起点，其左边围成的区域就是其中一个多边形
遍历的方向如下：
最外面的那个为无限面
求沿着逆时针转的最多的一条边作为下一条边方法就是取反向边顺时针转动的第一条，这样子更加的方便
// 平面直线图（PSGL）实现
struct PSLG {int n, m, face_cnt;double x[maxn], y[maxn];vector<Edge> edges;vector<int> G[maxn];int vis[maxn*2]; // 每条边是否已经访问过int left[maxn*2]; // 左面的编号(该边在哪个面内)int prev[maxn*2]; // 相同起点的上一条边（即顺时针旋转碰到的下一条边）的编号vector<Polygon> faces;double area[maxn]; // 每个polygon的面积void init(int n) {this->n = n;for(int i = 0; i < n; i++) G[i].clear();edges.clear();faces.clear();}// 有向线段from->to的极角double getAngle(int from, int to) {return atan2(y[to]-y[from], x[to]-x[from]);}void AddEdge(int from, int to) {edges.push_back((Edge){from, to, getAngle(from, to)});edges.push_back((Edge){to, from, getAngle(to, from)});m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}// 找出faces并计算面积void Build() {for(int u = 0; u < n; u++) {// 给从u出发的各条边按极角排序int d = G[u].size();for(int i = 0; i < d; i++) for(int j = i+1; j < d; j++) // 这里偷个懒，假设从每个点出发的线段不会太多if(edges[G[u][i]].ang > edges[G[u][j]].ang) swap(G[u][i], G[u][j]);for(int i = 0; i < d; i++)prev[G[u][(i+1)%d]] = G[u][i]; //u点出发的第i条边顺时针转的第一条边是prev[i]}memset(vis, 0, sizeof(vis));face_cnt = 0;for(int u = 0; u < n; u++)for(int i = 0; i < G[u].size(); i++) {int e = G[u][i]; //逆时针转的第i条边if(!vis[e]) { // 逆时针找圈face_cnt++;Polygon poly;for(;;) {vis[e] = 1; left[e] = face_cnt;int from = edges[e].from;poly.push_back(Point(x[from], y[from]));e = prev[e^1]; //反向边顺时针第一条if(e == G[u][i]) break; //回到原点assert(vis[e] == 0);}faces.push_back(poly);}}for(int i = 0; i < faces.size(); i++) {area[i] = PolygonArea(faces[i]);}}
};