本文主要是介绍hdu 4629 Burning（二维图形学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二维图形学，还是相当烦人的
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-8; const int MAXN = 55; const int MAXNUM = 25000; int nump, n; inline int dbCmp(const double x, const double y) {if ( fabs(x-y) < eps) return 0;return x<y?-1:1; }struct point {double x, y;point(){}point(double a, double b){x = a; y = b;}void getin(){scanf("%lf%lf", &x, &y);}bool operator < (const point & a) const{return -1 == dbCmp(x,a.x);}bool operator == (const point & a) const{return 0 == dbCmp(x,a.x);}point operator - (const point & a){return point(x-a.x, y-a.y);}double operator * (const point &a){return x*a.y-y*a.x;} }tpp[MAXNUM]; // 临时数据 double getCal(point frm, point ta, point tb) // {return (ta-frm)*(tb-frm); } struct line {point a, b;double A,B,C;int sz; // sz == 0 : up+, down-;line(){}line(point c, point d){a = c, b = d;}bool operator < (const line & e) const{return -1 == dbCmp(a.y+b.y, e.a.y+e.b.y);}int isCross(const line & e){if (getCal(e.a, a, b) * getCal(e.b, a, b)<0.0) return 1;return 0;}void operator *(const line &exa) const{tpp[nump++] = point((B*exa.C-exa.B*C)/(exa.B*A-B*exa.A), 0.0);}void mset(double x1, double x2){a.x = x1; b.x = x2;a.y = (C+A*x1)/-B;b.y = (C+A*x2)/-B;} }tpl[MAXN*3]; struct triangles {point pt[3];line mlin[3];void getin(){pt[0].getin(); pt[1].getin(); pt[2].getin();for (int i = 0; i< 3; ++i){int ii = (i+1)%3;if (pt[i].x < pt[ii].x) mlin[i] = line(pt[i], pt[ii]);else mlin[i] = line(pt[ii], pt[i]);mlin[i].A = pt[i].y - pt[ii].y;mlin[i].B = pt[ii].x - pt[i].x;mlin[i].C = pt[i].x*(-mlin[i].A) - pt[i].y*(mlin[i].B);if (dbCmp(pt[i].x, pt[ii].x) == 0){mlin[i].sz = 0;}else{int tt = (i+2)%3;if (getCal(mlin[i].a, mlin[i].b, pt[tt]) < 0.0)mlin[i].sz = -1;elsemlin[i].sz = 1;}}}void getCross(const triangles & exa){for (int i = 0; i< 3; ++i){for (int j = 0; j< 3; ++j){if (mlin[i].isCross(exa.mlin[j])){mlin[i]*exa.mlin[j];}}}} }mtr[MAXN]; // 三角形 double res[MAXN]; int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint t;scanf("%d", &t);while (t--){scanf("%d", &n);nump = 0;int cnt = 0;for (int i = 0; i< n; ++i){mtr[i].getin();tpp[nump++] = mtr[i].pt[0];tpp[nump++] = mtr[i].pt[1];tpp[nump++] = mtr[i].pt[2];res[i] = 0.0;}for (int i = 0; i< n; ++i){for (int j = i+1; j< n; ++j){mtr[i].getCross(mtr[j]);}}sort(tpp, tpp+nump);nump = unique(tpp, tpp+nump) - tpp;for (int i = 1; i< nump; ++i){cnt = 0;for (int j = 0; j< n; ++j){for (int k = 0; k< 3; ++k){if (mtr[j].mlin[k].a.x <= tpp[i-1].x && mtr[j].mlin[k].b.x >= tpp[i].x){tpl[cnt] = mtr[j].mlin[k];tpl[cnt++].mset(tpp[i-1].x, tpp[i].x);}}}sort(tpl, tpl+cnt);int tp = 1;for (int j = 1; j< cnt; ++j){res[tp] += (tpp[i].x-tpp[i-1].x)*(tpl[j].a.y - tpl[j-1].a.y + tpl[j].b.y - tpl[j-1].b.y)/2;tp += tpl[j].sz;}}for (int i = 1; i<= n; ++i){printf("%.10lf\n", res[i]);}}return 0; }
这篇关于hdu 4629 Burning（二维图形学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
