总体思路参考了 这里。
细节：1.控制精度，虽然这题没卡精度，不过还是要控制一下。
之前 bool operator<( const Point& A, const Point& B ) 函数没有控制精度，导致了相当大的误差。
2.三点共线的点判掉，虽然不影响结果，但是可以减少点的数目
3.扫入线扫出线的判断：判断第三个点在那两点所形成的的直线的上方还是下方，上方为扫入线, 下方为扫出线
#include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <algorithm> using namespace std; const int MAXN = 20010; const double eps = 1e-9; struct Point { double x, y; int type; Point( double x = 0, double y = 0, int tp = 0 ): x(x), y(y), type(tp) { } void read_Point() { scanf( "%lf%lf", &x, &y ); return; } }; struct Line { Point a, b; //线段起点，终点 int type; //标记扫入线还是扫出线 Line() {} Line( Point& x, Point& y, int tp ): a(x), b(y), type(tp) {} }; int cntX; vector<double> Lx; vector<Line> line; vector<Point> qujian[MAXN]; double ans[160]; typedef Point Vector; inline int dcmp( double x ) //控制精度 { if ( fabs(x) < eps ) return 0; else return x < 0 ? -1 : 1; } Vector operator+( Vector A, Vector B ) //向量加 { return Vector( A.x + B.x, A.y + B.y ); } Vector operator-( Vector A, Vector B ) //向量减 { return Vector( A.x - B.x, A.y - B.y ); } Vector operator*( Vector A, double p ) //向量数乘 { return Vector( A.x * p, A.y * p ); } Vector operator/( Vector A, double p ) //向量数除 { return Vector( A.x / p, A.y / p ); } bool operator<( const Point& A, const Point& B ) //两点比较 { return dcmp( A.x - B.x ) < 0 || ( dcmp( A.x - B.x ) == 0 && dcmp( A.y - B.y ) < 0 ); } bool operator==( const Point& a, const Point& b ) //两点相等 { return dcmp( a.x - b.x ) == 0 && dcmp( a.y - b.y ) == 0; } double Dot( Vector A, Vector B ) //向量点乘 { return A.x * B.x + A.y * B.y; } double Length( Vector A ) //向量模 { return sqrt( Dot( A, A ) ); } double Angle( Vector A, Vector B ) //向量夹角 { return acos( Dot(A, B) / Length(A) / Length(B) ); } double Cross( Vector A, Vector B ) //向量叉积 { return A.x * B.y - A.y * B.x; } double Area2( Point A, Point B, Point C ) //向量有向面积 { return Cross( B - A, C - A ); } Vector Rotate( Vector A, double rad ) //向量旋转 { return Vector( A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad) ); } Vector Normal( Vector A ) //向量单位法向量 { double L = Length(A); return Vector( -A.y / L, A.x / L ); } Point GetLineIntersection( Point P, Vector v, Point Q, Vector w ) //两直线交点 { Vector u = P - Q; double t = Cross( w, u ) / Cross( v, w ); return P + v * t; } double DistanceToLine( Point P, Point A, Point B ) //点到直线的距离 { Vector v1 = B - A, v2 = P - A; return fabs( Cross( v1, v2 ) ) / Length(v1); } double DistanceToSegment( Point P, Point A, Point B ) //点到线段的距离 { if ( A == B ) return Length( P - A ); Vector v1 = B - A, v2 = P - A, v3 = P - B; if ( dcmp( Dot(v1, v2) ) < 0 ) return Length(v2); else if ( dcmp( Dot(v1, v3) ) > 0 ) return Length(v3); else return fabs( Cross( v1, v2 ) ) / Length(v1); } Point GetLineProjection( Point P, Point A, Point B ) // 点在直线上的投影 { Vector v = B - A; return A + v*( Dot(v, P - A) / Dot( v, v ) ); } bool SegmentProperIntersection( Point a1, Point a2, Point b1, Point b2 ) //线段相交，交点不在端点 { double c1 = Cross( a2 - a1, b1 - a1 ), c2 = Cross( a2 - a1, b2 - a1 ), c3 = Cross( b2 - b1, a1 - b1 ), c4 = Cross( b2 - b1, a2 - b1 ); return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0; } /******************以上模板********************/ int N; void init() { int len = line.size(); for ( int i = 0; i < len; ++i ) for ( int j = i + 1; j < len; ++j ) { //如果线段相交 if ( SegmentProperIntersection( line[i].a, line[i].b, line[j].a, line[j].b ) ) { //获得交点 Point pp = GetLineIntersection( line[i].a, line[i].b - line[i].a, line[j].a, line[j].b - line[j].a ); Lx.push_back( pp.x ); } } sort( Lx.begin(), Lx.end() ); cntX = unique( Lx.begin(), Lx.end() ) - Lx.begin(); return; } void GetAns() { for ( int i = 0; i <= N; ++i ) ans[i] = 0.0; for ( int i = 0; i < cntX - 1; ++i ) { int dep = 0; //覆盖度 int sz = qujian[i].size(); double &st = Lx[i], &ed = Lx[i + 1]; for ( int j = 0; j < sz - 1; ++j ) { dep += qujian[i][j].type; ans[dep]+=(ed-st)*(qujian[i][j+1].x-qujian[i][j].x+qujian[i][j+1].y-qujian[i][j].y)/2.0; } } for ( int i = 1; i <= N; ++i ) printf( "%.10lf ", ans[i] ); return; } //void show() //{ // for ( int i = 0; i < cntX - 1; ++i ) // { // int sz = qujian[i].size(); // for ( int j = 0; j < sz; ++j ) // { // printf( "%.6f %.6f %d ", qujian[i][j].x, qujian[i][j].y, qujian[i][j].type ); // } // puts("****************** "); // } //} void solved() { init(); for ( int i = 0; i < cntX; ++i ) qujian[i].clear(); int len = line.size(); //遍历每个线段 for ( int i = 0; i < len; ++i ) { //查询线段左端点在Lx的起始位置 int j = lower_bound( Lx.begin(), Lx.begin() + cntX, line[i].a.x ) - Lx.begin(); //遍历线段横跨的区间 for ( ; j < cntX - 1; ++j ) { double st = Lx[j], ed = Lx[j + 1]; if ( dcmp( line[i].b.x - ed ) < 0 ) break; Point p1 =
GetLineIntersection( line[i].a, line[i].b-line[i].a, Point(st,0.0,0), Point(0,1.0,0)); Point p2 =
GetLineIntersection( line[i].a, line[i].b-line[i].a, Point(ed,0.0,0), Point(0,1.0,0)); qujian[j].push_back( Point( p1.y, p2.y, line[i].type ) ); } } for ( int i = 0; i < cntX - 1; ++i ) sort( qujian[i].begin(), qujian[i].end() ); GetAns(); return; } //两点确定直线一般式 void GetABC( Point a, Point b, double& A, double& B, double& C ) { if( dcmp( a.x - b.x ) == 0 ) B = 0.0; else B = -1.0; A = ( b.y - a.y ) / ( b.x - a.x ); C = a.y - A * a.x; return; } //判断扫入扫出线 int SaoRuSaoChu( Point p1, Point p2, Point c ) { double A, B, C; GetABC( p1, p2, A, B, C ); if ( dcmp( B ) == 0 ) return 0; double res = A * c.x + B * c.y + C; return dcmp( res ) < 0 ? 1 : -1; //扫入线 1, 扫出线 -1 } int main() { //freopen( "1009.in", "r", stdin ); //freopen( "s.txt", "w", stdout ); int T; scanf( "%d", &T ); while ( T-- ) { Lx.clear(); line.clear(); scanf( "%d", &N ); for ( int i = 0; i < N; ++i ) { Point p[3]; for ( int j = 0; j < 3; ++j ) p[j].read_Point(); //判断三点共线 if ( dcmp( Cross( p[1] - p[0], p[2] - p[0] ) == 0 ) ) continue; for ( int j = 0; j < 3; ++j ) { Lx.push_back( p[j].x ); int k = j + 1; if ( k >= 3 ) k = 0; Line tmpL( p[j], p[k], 0 ); //令a点为线段左端点, b为线段右端点 if ( dcmp( tmpL.b.x - tmpL.a.x ) < 0 ) swap( tmpL.a, tmpL.b ); int m = 3 - j - k; //除了构成线段的两点外的那个点 //判断扫入扫出线 int tp = SaoRuSaoChu( p[j], p[k], p[m] ); //如果这条线垂直于x轴,既不是扫入也不是扫出线 if ( tp == 0 ) continue; //得到扫入扫出线 tmpL.type = tp; line.push_back( tmpL ); } } solved(); //printf("lineN = %d cntX=%d ", (int)line.size(), (int)Lx.size() ); //show(); } return 0; }