程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4629 計算幾何 掃描線

hdu 4629 計算幾何 掃描線

編輯:C++入門知識

思路: 把所有線段的端點和所有的交點都放到一個數組中,並從小到大排序,然後對於每個x都畫一條從下往上的垂直線,

我們枚舉每兩個相鄰的x,單獨計算它們之間的面積,這裡我們從下往上掃過去。

那麼我們如何知道哪塊面積計算了幾次呢,我們用一個 ”度“ 來表示這塊面積被覆蓋了幾次。

以圖中第二條和第三條豎線之間的面積為例, 最下面的一塊一定是計算0次的,度為0, 那麼當它從下往上經過第一條邊時,度加1,那麼上面一塊的梯形就是覆蓋一次,再網上穿過一條線段,度再加1,所以這塊三角形的被覆蓋了兩次,接下來都是類似的情況, 知道掃完所有兩條豎線之間的線段為止。

 


如何處理度呢?我們把度的信息放在線段上, 對於輸入的三角形 ABC, 如何我們要取線段AB, 那麼如果C在AB上方讓這條線段的度為1,在下方就是-1(可以用叉積),當然要排除AB與x軸垂直的情況。

 


代碼注釋的很詳細:

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const double eps = 1e-8;
#define pb push_back
inline int dcmp(double x) {
    if (fabs(x) < eps)
        return 0;
    return x > eps ? 1 : -1;
}
struct point {
    double x, y;
    point() {
    }
    point(const double &x, const double &y) :
            x(x), y(y) {
    }
    inline void in() {
        scanf("%lf%lf", &x, &y);
    }
    bool operator <(const point &t) const {
        return x + eps < t.x || (fabs(x - t.x) < eps && y + eps < t.y);
    }
    bool operator ==(const point &t) const {
        return !dcmp(x - t.x) && !dcmp(y - t.y);
    }
};
struct Line {
    point a, b;
    int tp;
    Line(const point &a, const point &b, const int &tp) :
            a(a), b(b), tp(tp) {
    }
    Line() {
    }
    bool operator <(const Line &t) const {
        return a < t.a || (a == t.a && b < t.b);
    }
};
double cross(const point &o, const point &a, const point &b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool segSegIntersect(const point &a, const point &b, const point &l, const point &r) { // 判兩線段是否相交
    if (cross(a, b, l) * cross(a, b, r) < eps
            && cross(l, r, a) * cross(l, r, b) < eps)
        return 1; // 規范相交
    return 0;
}
//********兩直線求交點, 先必須判是否相交(注意排除共線)
point intersect(const point &a, const point &b, const point &l, const point &r) {
    point ret = a;
    double t = ((a.x - l.x) * (l.y - r.y) - (a.y - l.y) * (l.x - r.x))
            / ((a.x - b.x) * (l.y - r.y) - (a.y - b.y) * (l.x - r.x));
    ret.x += (b.x - a.x) * t;
    ret.y += (b.y - a.y) * t;
    return ret;
}
int n;

Line line[22504], res[22504]; //line記錄所有三角形的線段,   res記錄夾在相鄰兩個x豎線之間的線段
double X[22504];			//記錄所有端點和交點的X
int c1, c2, c3;				//   line的個數,     res的個數    X的個數

double ans[55];

int main() {
    int i, j, k, cas;
    scanf("%d", &cas);
    while (cas--) {
        c1 = c2 = c3 = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            point a, b, c, tp[5];
            for (j = 0; j < 3; j++) {
                tp[j].in();
                X[c3++] = tp[j].x;
            }
            if (!dcmp(cross(tp[0], tp[1], tp[2])))		//三點共線特判掉,不特判也沒關系的
                continue;
            for (j = 0; j < 3; j++)					//兩兩枚舉三角形的邊
                for (k = j + 1; k < 3; k++) {
                    a = tp[j];
                    b = tp[k];
                    if (a.x == b.x)					//排除與x軸垂直的線段
                        continue;
                    if (b < a)
                        swap(a, b);
                    c = tp[3 - j - k];
                    line[c1++] = Line(a, b, dcmp(cross(a, b, c)));    //叉積判上下方非常方便
                }
        }
		//得到所有線段的交點
        for (i = 0; i < c1; i++)	
            for (j = i + 1; j < c1; j++) {
                if (!segSegIntersect(line[i].a, line[i].b, line[j].a,
                        line[j].b))
                    continue;
                point tp = intersect(line[i].a, line[i].b, line[j].a,
                        line[j].b);
                X[c3++] = tp.x;
            }
        sort(X, X + c3);		//X排序去重
		c3 = unique(X, X+c3)-X;
        for (i = 0; i <= n; i++)
            ans[i] = 0.0;
        for (i = 1; i < c3; i++) {    //枚舉相鄰的X  即  X[i-1] 與X[i]
            c2 = 0;
            for (j = 0; j < c1; j++)		//枚舉所有三角形的邊
                if (line[j].a.x <= X[i - 1] && X[i] <= line[j].b.x) {			//線段在該區域裡面,確保有交點
                    point a = intersect(line[j].a, line[j].b, point(X[i-1], 0),
                            point(X[i-1], 1));
                    point b = intersect(line[j].a, line[j].b, point(X[i], 0),
                            point(X[i], 1));
                    res[c2++] = Line(a, b, line[j].tp);		//把夾在 X[i-1] 與X[i]這兩條豎線之間的線段保存下來
                }
            sort(res, res + c2);			
            if (c2) {
                int deep = res[0].tp;
                for (j = 1; j < c2; j++) { //從下往上遍歷所有線段並計算面積
                    double h = res[j].b.x - res[j].a.x;
                    double b = fabs(res[j - 1].a.y - res[j].a.y)
                            + fabs(res[j - 1].b.y - res[j].b.y);
                    if (deep)
                        ans[deep] += b * h / 2;	
                    deep += res[j].tp;		//修改度
                }
            }
        }

        for (i = 1; i <= n; i++)
            printf("%.10f\n", ans[i]);
    }
    return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved