Chlience

【题解】BZOJ 1845 [CQOI2005]三角形面积并
Problem给出 $n$ 个三角形,求其面积并Thought第一次做计算几何的题(雾首先考虑如何计算三角形面积并...
扫描右侧二维码阅读全文
18
2019/01

【题解】BZOJ 1845 [CQOI2005]三角形面积并

Problem

给出 $n$ 个三角形,求其面积并

Thought

第一次做计算几何的题(雾

首先考虑如何计算三角形面积并:
如果有一段区间 $[l,r]$ 中不含有任何一个交点,那么称它为平凡的

在一段平凡的区间中,不存在某个三角形新覆盖了另外一个三角形,或者说某个三角形重新露了出来
那么在这一段区间中高度应该是连续变化的(面积的改变只取决于最大的三角形)

那么其总面积可以利用梯形的公式来求,利用上下底或者是中位线的长度都是可以的

只需要扫描线一波扫过去就好了

具体如何求线段交点啥的先看代码吧,之后会专门写一篇博客来讲这些

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-8;
typedef pair <double , double> Pair;
struct Vector {
    double x, y;
    Vector operator + (const Vector a) const {return Vector{x + a.x, y + a.y};}
    Vector operator - (const Vector a) const {return Vector{x - a.x, y - a.y};}
    double operator * (const Vector a) const {return x * a.y - y * a.x;}
    Vector operator * (double a) {return Vector{x * a, y * a};}
};
struct Triangle {
    Vector p[3];
    Vector& operator [] (int x) {return p[x];}
}t[N];

double X[N * N * 15];
Pair sta[N];
int n, cnt, top;

int read();
bool crossCheck(Vector, Vector, Vector, Vector);
Vector crossPos(Vector, Vector, Vector, Vector);
double get(double);
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in" , "r", stdin);
    #endif
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        for(int j = 0; j < 3; ++ j)
            scanf("%lf %lf", &t[i][j].x, &t[i][j].y);
        X[++ cnt] = t[i][0].x;
        X[++ cnt] = t[i][1].x;
        X[++ cnt] = t[i][2].x;
        for(int j = 1; j < i; ++ j)
            for(int k = 0; k < 3; ++ k)
                for(int l = 0; l < 3; ++ l)
                    if(crossCheck(t[i][k], t[i][(k + 1) % 3], t[j][l], t[j][(l + 1) % 3]))
                        X[++ cnt] = crossPos(t[i][k], t[i][(k + 1) % 3] - t[i][k], t[j][l], t[j][(l + 1) % 3] - t[j][l]).x;
    }

    sort(X + 1, X + cnt + 1);
    cnt = unique(X + 1 , X + cnt + 1) - X - 1;
    double ans = 0;
    for(int i = 2; i <= cnt; ++ i) {
        double D = get((X[i] + X[i - 1]) / 2);
        ans += (X[i] - X[i - 1]) * D;
    }
    printf("%.2f\n", ans - eps);
}
bool crossCheck(Vector pl, Vector pr, Vector ql, Vector qr) {
    if(fabs((pr - pl) * (qr - ql)) < eps) return 0;
    Vector p = crossPos(pl , pr - pl , ql , qr - ql);
    if(p.x + eps < min(pl.x, pr.x) || p.x - eps > max(pl.x, pr.x)) return 0;
    if(p.x + eps < min(ql.x, qr.x) || p.x - eps > max(ql.x, qr.x)) return 0;
    return 1;
}
Vector crossPos(Vector p1, Vector v1, Vector p2, Vector v2) {
    return v1 * (((p2 - p1) * v2) / (v1 * v2)) + p1;
}
double get(double x) {
    top = 0;
    for(int i = 1; i <= n; ++ i) {
        double U = - 1000000 , D = 1000000;
        Vector a = Vector{x, - 1000000};
        Vector b = Vector{x, 1000000};
        for(int j = 0; j < 3; ++ j) {
            if(crossCheck(t[i][j], t[i][(j + 1) % 3], a, b)) {
                Vector p = crossPos(t[i][j], t[i][(j + 1) % 3] - t[i][j], a, b - a);
                U = max(U, p.y); D = min(D, p.y);
            }
        }
        if(U >= D)
            sta[++ top] = {D, U};
    }
    sort(sta + 1, sta + top + 1);
    double ans = 0, last = - 1000000;
    for(int i = 1; i <= top; ++ i) {
        if(last >= sta[i].second) continue;
        ans += min(sta[i].second - sta[i].first, sta[i].second - last);
        last = max(last, sta[i].second);
    }
    return ans;
}
Last modification:March 5th, 2019 at 07:25 am

Leave a Comment