题意： 给出一些直线。这些直线将平面分成好多块。求这些块中各个封闭图形的面积。
分析： ①我们需要求出两两直线的交点； ②再对每条直线上的交点排序，藉此来离散出所有的线段（正反两条边）； ③对于连向一个点的几条线段，对它们进行极角排序，相邻的两条线段我们给它们之间连一条边，我们脑补一下应该可以知道怎样可以保证逆时针连边； ④找循环，利用叉积求面积。
的调试真心不爽…
;const int MAXN = 100;const int MAXE = MAXN*MAXN<<1;const double eps = 1e-8;typedef double DB;int n;#define sqr(x) ((x)*(x))struct pot{double x, y;pot(double x = 0, double y = 0):x(x), y(y){}(sqr(x)+sqr(y));}inline void read() {scanf(“%lf%lf”, &x, &y);}inline pot unit(){double d = len();return pot(x/d, y/d);}(y, x);}};typedef pot vec;struct Line{pot p;vec v;Line(){}Line(pot p, vec v):p(p), v(v){}}lines[MAXN];vector<pot> points;struct Edge{int sz;int head[MAXE], to[MAXE], ne[MAXE];Edge(){sz = 0;memset(head, -1, sizeof(head));}inline void add(int u, int v){to[sz] = v;ne[sz] = head[u];head[u] = sz++;}}E;int next[MAXE];bool vis[MAXE];vector<DB> ans;inline int dcmp(double x){if(fabs(x) <= eps) return 0;else return x>0?1:-1; }inline pot operator + (const vec &a, const vec &b) {return vec(a.x+b.x, a.y+b.y);}inline pot operator – (const vec &a, const vec &b) {return vec(a.x-b.x, a.y-b.y);}* (const vec &a, const vec &b) {return a.x*b.x+a.y*b.y;}^ (const vec &a, const vec &b) {return a.x*b.y-a.y*b.x;}inline pot operator * (const vec &a, double k) {return vec(a.x*k, a.y*k);}inline pot operator / (const vec &a, double k) {return vec(a.x/k, a.y/k);}< (const vec &a, const vec &b) {return dcmp(a.x-b.x) < 0 || (dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) < 0);}== (const vec &a, const vec &b) {return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;}inline pot get_line_intersection(const pot &p, const vec &v, const pot &q, const vec &w){vec u = p-q;double t = (w^u)/(v^w);return p+v*t;}inline bool parallel(const Line &a, const Line &b) {return dcmp(a.v^b.v) == 0;}inline int get_pot_id(const pot &p) {return lower_bound(points.begin(), points.end(), p)-points.begin();}inline bool cmp(DB a, DB b) {return dcmp(a-b) == 0;}inline void init(){scanf(“%d”, &n);for(int i = 0; i < n; ++i){pot a, b;a.read();b.read();lines[i] = Line(a, b-a);}for(int i = 0; i < n; ++i)for(int j = i+1; j < n; ++j)if(!parallel(lines[i], lines[j]))points.pb(get_line_intersection(lines[i].p, lines[i].v, lines[j].p, lines[j].v));sort(points.begin(), points.end());points.erase(unique(points.begin(), points.end()), points.end());for(int i = 0; i < n; ++i){vector<DB> nodes;vec d = lines[i].v.unit();for(int j = 0; j < n; ++j)if(!parallel(lines[i], lines[j])){pot inter = get_line_intersection(lines[i].p, lines[i].v, lines[j].p, lines[j].v);nodes.pb((inter-lines[i].p)*d);}sort(nodes.begin(), nodes.end());nodes.erase(unique(nodes.begin(), nodes.end(), cmp), nodes.end());for(int j = 1, sz = nodes.size(); j < sz; ++j){int a = get_pot_id(lines[i].p+d*nodes[j]);int b = get_pot_id(lines[i].p+d*nodes[j-1]);E.add(a, b);E.add(b, a);}}memset(next, -1, sizeof(next));for(int i = 0, sz = points.size(); i < sz; ++i){vector<pair<DB, int> > PA;for(int j = E.head[i]; j != -1; j = E.ne[j])PA.pb(mp((points[E.to[j]]-points[i]).ang(), j));sort(PA.begin(), PA.end());for(int j = 0, sz = PA.size(); j < sz; ++j)next[PA[(j+1)%sz].se^1] = PA[j].se;}}inline void work(){for(int i = 0; i < E.sz; ++i)if(!vis[i]){stack<int> s;int j = i;do{if(!s.empty() && (s.top()^1) == j)s.pop();else s.push(j);vis[j] = true;j = next[j];if(j == -1) break;}while(!vis[j]);if(i == j){DB area = 0;while(!s.empty()){area += (points[E.to[s.top()^1]]^points[E.to[s.top()]]);s.pop();}area *= 0.5;if(dcmp(area) > 0)ans.pb(area);}}}inline void print(){printf(“%d\n”, ans.size());sort(ans.begin(), ans.end());for(int i = 0, sz = ans.size(); i < sz; ++i)printf(“%.4lf\n”, ans[i]);}int main(){init();work();print();return 0; }
，生气是拿别人做错的事来惩罚自己
