UVa 11759 - IBM Fencing

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

給定 N 個凸包，保證凸包之間不會有交點，而依據分層，奇數層使用金屬圍欄，偶數層使用木製圍欄，請問分別為需要多少材料。

Sample Input

8
8 112 134 73 141 41 119 32 82 54 50 92 43 124 65 132 103
6 119 119 102 119 94 101 102 83 119 83 127 101
8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87
6 70 97 56 97 49 85 56 73 70 73 77 85
8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181
4 115 226 58 226 51 167 132 167
4 113 212 65 212 65 172 113 172
5 99 205 83 206 71 187 91 179 105 189
2
4 0 0 100 0 100 100 0 100
4 1000 1000 1100 1000 1100 1100 1000 1100
0

Sample Output

Case 1:
Total Number of Communities 2
Total Cost:
Steel Fence: 0.09047417 Million Yuan
Wooden Fence: 0.03190241 Million Yuan
  
Case 2:
Total Number of Communities 2
Total Cost:
Steel Fence: 0.08000000 Million Yuan
Wooden Fence: 0.00000000 Million Yuan

Solution

這裡需要對 N 個凸包做相互關係判斷，建造出 tree 圖，根據樹圖計算分層。

兩個凸包判定可以在 O(log n) 時間內完成，因此建造會在 O(n^2 log n)。

找到多邊形分層圖之間的關係，只會有完全包裹和完全沒交集兩種情況。利用掃描線可以找到兩個相鄰多邊形，要不與其同一層，要不就是上一層。因此可以在 n log n 時間內找到，考慮邊的個數問題，複雜度上提 O(nm log nm) 不如暴力窮舉兩個多邊形做判定 O(n^2 m)，在都是凸多邊形的情況 O(n^2 log m)。掃描線掃了一連串結果，還要處理同一多邊形端點相同的線段，利用隨機擾動處理垂直線 … 等，自找苦吃，暴力完勝。

#include <stdio.h>
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    int  label;
    Pt(double a = 0, double b = 0, int c = 0):
    	x(a), y(b), label(c) {}
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)	return x < a.x;
        if (fabs(y - a.y) > eps)	return y < a.y;
        return false;
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
// this problem
vector<int> g[512];

struct Polygon { // convex
    vector<Pt> p;
    int contain(Polygon &a) {
        int n = p.size();
        if(n < 3)	return false;
        Pt q = a.p[0];
        if(cross(p[0], q, p[1]) > eps)		return 0;
        if(cross(p[0], q, p[n-1]) < -eps)	return 0;
        int l = 2, r = n - 1;
        int line = -1;
        while(l <= r) {
            int mid = (l + r)>>1;
            if(cross(p[0], q, p[mid]) > -eps) {
                line = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        return cross(p[line-1], q, p[line]) < eps;
    }
};
Polygon poly[512];

int parent[32767], visited[32767], depth[32767];
void bfs(int u) {
    int v;
    queue<int> Q;
    Q.push(u);
    visited[u] = 1, depth[u] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (depth[v] < depth[u] + 1) {
                depth[v] = depth[u] + 1;
                visited[v] = 1, parent[v] = u;
                Q.push(v);
            }
        }
    }
}
int main() {
    int N, M, cases = 0;
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++) {
            scanf("%d", &M);
            poly[i].p.resize(M);
            for (int j = 0; j < M; j++)
                scanf("%lf %lf", &poly[i].p[j].x, &poly[i].p[j].y);
            double mnx = poly[i].p[0].x;
            int idx = 0;
            for (int j = 0; j < M; j++) {
                if (poly[i].p[j].x < mnx)
                    mnx = poly[i].p[j].x, idx = j;
            }
            if (cross(poly[i].p[idx], poly[i].p[(idx+1)%M], poly[i].p[(idx-1+M)%M]) < eps)
                reverse(poly[i].p.begin(), poly[i].p.end());
        }
        
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j)	continue;
                if (poly[i].contain(poly[j]))
                    g[i].push_back(j);
            }
        }
        
        for (int i = 0; i < N; i++) {
            visited[i] = 0, parent[i] = -1, depth[i] = 0;
        }
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0)
                bfs(i);
        }		
        int communities = 0;
        double Acost = 0, Bcost = 0;
        for (int i = 0; i < N; i++) {
            if (parent[i] == -1)
                communities++;
            double tmp = 0;
            for (int j = 0, k = poly[i].p.size() - 1; j < poly[i].p.size(); k = j++)
                tmp += dist(poly[i].p[j], poly[i].p[k]);
            if (depth[i]&1)
                Acost += tmp;
            else
                Bcost += tmp/2;
        }
        
        printf("Case %d:\n", ++cases);
        printf("Total Number of Communities %d\n", communities);
        printf("Total Cost:\n");
        printf("Steel Fence: %.8lf Million Yuan\n", Acost / 10000.0);
        printf("Wooden Fence: %.8lf Million Yuan\n", Bcost / 10000.0);
        puts("");
    }
    return 0;
}
/*
8
8 112 134 73 141 41 119 32 82 54 50 92 43 124 65 132 103
6 119 119 102 119 94 101 102 83 119 83 127 101
8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87
6 70 97 56 97 49 85 56 73 70 73 77 85
8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181
4 115 226 58 226 51 167 132 167
4 113 212 65 212 65 172 113 172
5 99 205 83 206 71 187 91 179 105 189

2
4 0 0 100 0 100 100 0 100
4 1000 1000 1100 1000 1100 1100 1000 1100
0
*/