题意：给n个三角形，分别求覆盖1次~n次的总面积
思路： 对每个y坐标作一条平行于x轴的直线，按直线从下往上处理，每两条直线之间为若干梯形（也可以是三角形）首尾相连的情况，从左扫到右时，用一个变量cnt记录当前区域被覆盖的次数，遇到入边cnt++，遇到出边cnt--，边扫边更新答案。入边表示这条边的右边在三角形内部，出边表示这条边的右边在三角形的外部。思路并不复杂，只是代码稍长点。
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define X first
#define Y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a)) typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull; //#ifndef ONLINE_JUDGE
void RI(vector<int>&a,int n){a.resize(n);for(int i=;i<n;i++)scanf("%d",&a[i]);}
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?:-;
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>
void print(T*p, T*q){int d=p<q?:-;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}
//#endif
template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}
template<typename T>
void V2A(T a[],const vector<T>&b){for(int i=;i<b.size();i++)a[i]=b[i];}
template<typename T>
void A2V(vector<T>&a,const T b[]){for(int i=;i<a.size();i++)a[i]=b[i];} const double PI = acos(-1.0);
const int INF = 1e9 + ;
const double EPS = 1e-8; /* -------------------------------------------------------------------------------- */ const int maxn = ; int dcmp(double a) {
if (abs(a) < EPS) return ;
return a > ? : -;
} struct Point {
double x, y;
void read() {
int x, y;
scanf("%d%d", &x, &y);
this->x = x;
this->y = y;
}
Point(double x, double y) {
this->x = x;
this->y = y;
}
Point() {}
Point operator - (const Point &that) const {
return Point(this->x - that.x, this->y - that.y);
}
bool operator < (const Point &that) const {
return dcmp(this->y - that.y) < || dcmp(this->y - that.y) == &&
dcmp(this->x - that.x) < ;
}
Point operator * (const double &m) const {
return Point(this->x * m, this->y * m);
}
};
struct Segment {
Point a, b;
Segment(Point a, Point b) {
this->a = a;
this->b = b;
}
Segment() {}
bool operator < (const Segment &that) const {
return dcmp(this->a.x + this->b.x - that.a.x - that.b.x) < ;
}
};
Point point[maxn * maxn * ];
Segment seg[maxn * ];
int type[maxn * ];
double ans[maxn]; double cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
} bool onMid(Point a, Point b, Point c) {
return dcmp(cross(c - a, b - a)) == ;
}
bool onLeft(Point a, Point b, Point c) {
return dcmp(cross(c - a, b - a)) < ;
}
bool Intersect(Segment A, Segment B) {
int r1 = dcmp(cross(A.b - A.a, B.a - A.a));
int r2 = dcmp(cross(A.b - A.a, B.b - A.a));
int r3 = dcmp(cross(B.b - B.a, A.a - B.a));
int r4 = dcmp(cross(B.b - B.a, A.b - B.a));
return (r1 ^ r2) || (r3 ^ r4);
}
Point getLineIntersection(Segment A, Segment B) {
Point u = A.a - B.a, v = A.b - A.a, w = B.b - B.a;
double t = cross(w, u) / cross(v, w);
return A.a - v * -t;
}
double Area(Segment A, Segment B) {
return fabs((A.a.x - B.a.x + A.b.x - B.b.x) * (A.a.y - A.b.y) / );
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
int T, n, cs, cp;
cin >> T;
while (T --) {
cin >> n;
cp = cs = ;
for (int i = ; i < n; i ++) {
Point p[];
for (int j = ; j < ; j ++) p[j].read();
if (onMid(p[], p[], p[])) continue;
sort(p, p + );
seg[cs ++] = Segment(p[], p[]);
seg[cs ++] = Segment(p[], p[]);
seg[cs ++] = Segment(p[], p[]);
if (onLeft(p[], p[], p[])) {
type[cs - ] = type[cs - ] = ;
type[cs - ] = -;
}
else {
type[cs - ] = type[cs - ] = -;
type[cs - ] = ;
}
}
for (int i = ; i < cs; i ++) {
for (int j = i + ; j < cs; j ++) {
if (Intersect(seg[i], seg[j]))
point[cp ++] = getLineIntersection(seg[i], seg[j]);
}
}
sort(point, point + cp);
vector<double> Y;
for (int i = ; i < cp; i ++) {
if (!i || dcmp(point[i].y - point[i - ].y) != ) Y.pb(point[i].y);
}
fillchar(ans, );
for (int i = ; i < Y.size(); i ++) {
vector<pair<Segment, int> > S;
for (int j = ; j < cs; j ++) {
if (dcmp(seg[j].a.y - Y[i - ]) <= && dcmp(seg[j].b.y - Y[i]) >= ) {
Point a = seg[j].a, b = seg[j].b;
double d = (b.x - a.x) / (b.y - a.y);
double x1 = a.x + d * (Y[i - ] - a.y), x2 = a.x + d * (Y[i] - a.y);
S.pb(mp(Segment(Point(x1, Y[i - ]), Point(x2, Y[i])), type[j]));
}
}
sort(all(S));
int cnt = ;
for (int j = ; j < S.size(); j ++) {
if (cnt) ans[cnt] += Area(S[j - ].X, S[j].X);
cnt += S[j].Y;
}
}
for (int i = ; i <= n; i ++) {
printf("%.10f\n", ans[i]);
}
} return ;
}