解題區/解題區 - UVa

UVa 10117 - Nice Milk

Problem

有一個凸多邊形的餅乾要沾牛奶，但是杯子的深度有限，最多沾 h 高，而最多拿 k 個邊去沾，請問最多沾到的面積為何？

Sample Input

1
2
3
4
5
6
4 2 1
1 0
3 0
5 2
0 4
0 0 0

Sample Output

1
7.46

Solution

最多只有 20 條邊，因此窮舉 C(20, k) 然後計算沒沾到沾到的最小面積為何。藉此得到最大沾有面積為多少。

沾到的面積計算採用半平面交的方式。如果使用該邊去沾牛奶，則將此邊往內推根據法向量內推 h 距離。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-10
#define MAXN 131072
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    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;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
Seg deq[MAXN];
vector<Pt> halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < eps)
    	front++;
    vector<Pt> ret;
    for (int i = front; i < rear; i++) {
        Pt p = getIntersect(deq[i], deq[i+1]);
        ret.push_back(p);
    }
    if (rear > front + 1) {
        Pt p = getIntersect(deq[front], deq[rear]);
        ret.push_back(p);
    } 
    return ret;
}
double calcArea(vector<Pt> p) {
    double ret = 0;
    int n = p.size();
    if(n < 3) return 0.0;
    for(int i = 0, j = n-1; i < n; j = i++)
        ret += p[i].x * p[j].y - p[i].y * p[j].x;
    return fabs(ret)/2;
}
Pt D[32];
int main() {
    int n, m;
    double h;
    while (scanf("%d %d %lf", &n, &m, &h) == 3 && n) {
        vector<Pt> O;
        Seg Oe[32];
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
            O.push_back(D[i]);
        }
        D[n] = D[0], O.push_back(D[0]);
        for (int i = 0; i < n; i++) {
            Pt a = D[i], b = D[i+1]; // \vec{ab}
            Pt nab(b.y - a.y, a.x - b.x); // normal vector
            double v = hypot(nab.x, nab.y);
            nab.x = nab.x / v * h, nab.y = nab.y / v * h;
            a = a - nab, b = b - nab;
            Oe[i] = Seg(a, b);
        }
        int A[32] = {};
        for (int i = 0; i < m; i++)
            A[i] = 1;
        sort(A, A+n);
        double area = calcArea(O), ret = 0;
        do {
            vector<Seg> segs;
            for (int i = 0; i < n; i++)
                if (A[i])
                    segs.push_back(Oe[i]);
                else
                    segs.push_back(Seg(O[i], O[i+1]));
            vector<Pt> convex = halfPlaneIntersect(segs);
            double d = calcArea(convex);
            ret = max(ret, area - d);
        } while (next_permutation(A, A+n));
        printf("%.2lf\n", ret);
    }
    return 0;
}
/*
4 2 1
1 0
3 0
5 2
0 4
4 1 1
1 0
3 0
5 2
0 4
0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 1475 - Jungle Outpost

Problem

有一個軍事基地在叢林深處隱藏，基地將會由 n 個塔台包圍保護。並且只能保護其凸包內的所有地區。

敵人可以摧毀一些塔，使得保護區的保護範圍縮小，使得基地給暴露出來。

在萬無一失的條件下，希望將基地建造在敵人需要摧毀最多塔台才能基地所在地。

Sample Input

1
2
3
4
5
6
7
8
9
10
3 
0 0 
50 50 
60 10 
5 
0 0 
0 10 
10 20 
20 10 
25 0

Sample Output

1
2
1
2

Solution

二分需要摧毀的塔台數 K，由於敵人最多摧毀 K 個塔台，就能將基地給找出來，也就是說任意炸掉連續區段的塔台，他們所產生出來的交集是存在的。如果沒有存在交集，則基地可以藏在那裏面，不管敵人怎麼摧毀都找不到基地在哪。

為什麼需要連續呢？分段結果肯定不好，涵蓋的面積也少，同時會被連續 K 的情況給包含，所以不用考慮分段。

N 很大，半平面交的誤差也很大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-9
#define MAXN 131072
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    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;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
Seg deq[MAXN];
int halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < eps)
    	front++;
    return front + 1 < rear;
//    vector<Pt> ret;
//	for (int i = front; i < rear; i++) {
//		Pt p = getIntersect(deq[i], deq[i+1]);
//		ret.push_back(p);
//	}
//	if (rear > front + 1) {
//		Pt p = getIntersect(deq[front], deq[rear]);
//		ret.push_back(p);
//	} 
//	return ret;
}
int testBlowUp(int m, Pt D[], int n) {
    vector<Seg> segs;
    for (int i = 0; i < n; i++) {
        Pt a = D[i], b = D[i + m];
        segs.push_back(Seg(b, a));
    }
    return halfPlaneIntersect(segs);
}
Pt D[131072];
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
            D[i + n] = D[i];
        }
        if (n <= 3) {
            puts("1");
            continue;
        }
        int l = 1, r = n - 2, mid, ret;
        while (l <= r) {
            mid = (l + r)/2;
            if(testBlowUp(mid, D, n))
                l = mid + 1, ret = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
3 
0 0 
50 50 
60 10 
5 
0 0 
0 10 
10 20 
20 10 
25 0
*/
Read More +
解題區/解題區 - UVa

UVa 1396 - Most Distant Point from the Sea

Problem

給一個逆時針順序的凸多邊形，找一個內接最大圓。求出最大半徑為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
4 
0 0 
10000 0 
10000 10000 
0 10000 
3 
0 0 
10000 0 
7000 1000 
6 
0 40 
100 20 
250 40 
250 70 
100 90 
0 70 
3 
0 0 
10000 10000 
5000 5001 
0

Sample Output

1
2
3
4
5000.000000 
494.233641 
34.542948 
0.353553

Solution

二分半徑 r，如果內側放置一個圓，則保證每一條邊到圓心距離都大於等於 r。

藉此嘗試將每一條邊往內推，計算半平面交集是否存在，往內推根據法向量內推 r 距離。

求半平面交需要 O(n log n)，二分又有一個 log k，所以效率必須是 O(n log n log k)。

關於是否需要半平面交還有一個擴充，由於這題不求半平面結果，單純詢問有交集與否，可以利用 2D randomized bounded LP，隨機順序放置半平面，維護最下方的最佳解，如果不存在就 O(n) 建立 (不存在的機率 1/i，因此 O(n)/n = O(1))，可以在 O(n) 完成，這麼一來速度也許還能再更快些。有空再來實作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-7
#define MAXN 32767
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    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;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
Pt getIntersect(Seg a, Seg b) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = a.s.y - a.e.y, b1 = a.e.x - a.s.x;
    c1 = a1 * a.s.x + b1 * a.s.y;
    a2 = b.s.y - b.e.y, b2 = b.e.x - b.s.x;
    c2 = a2 * b.s.x + b2 * b.s.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
Seg deq[MAXN];
int halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < -eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < -eps)
    	front++;
    return front + 1 < rear;
//    vector<Pt> ret;
//	for (int i = front; i < rear; i++) {
//		Pt p = getIntersect(deq[i], deq[i+1]);
//		ret.push_back(p);
//	}
//	if (rear > front + 1) {
//		Pt p = getIntersect(deq[front], deq[rear]);
//		ret.push_back(p);
//	} 
//	return ret;
}
int testRadius(double r, Pt D[], int n) {
    vector<Seg> segs;
    for (int i = 0, j = n-1; i < n; j = i++) {
        Pt a = D[j], b = D[i]; // \vec{ab}
        Pt nab(b.y - a.y, a.x - b.x); // normal vector
        double v = hypot(nab.x, nab.y);
        nab.x = nab.x / v * r, nab.y = nab.y / v * r;
        a = a - nab, b = b - nab;
        segs.push_back(Seg(a, b));
    }
    return halfPlaneIntersect(segs);
}
int main() {
    int n;
    Pt D[128];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        double l = 0, r = 10000, mid, ret;
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            if(testRadius(mid, D, n))
                l = mid, ret = mid;
            else
                r = mid;
        }
        printf("%lf\n", ret);
    }
    return 0;
}
/*
4 
0 0 
10000 0 
10000 10000 
0 10000 
3 
0 0 
10000 0 
7000 1000 
6 
0 40 
100 20 
250 40 
250 70 
100 90 
0 70 
3 
0 0 
10000 10000 
5000 5001 
0
*/
Read More +
解題區/解題區 - UVa

UVa 12587 - Reduce the Maintenance Cost

Problem

在 N 個城市，每個城市都要每月的基礎花費，而在城市之間有 M 條邊，市長安排在邊兩側的城市其一要負責維護這一條重要邊，而重要邊的維護花費為該邊移除後，導致任兩個城市之間無法相連的對數乘上該路長。

只需要將一條邊交給相鄰的其一城市維護即可，因此會將該城市的月花費上升，求一種分配方案使得城市的最大花費最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
2 1
5 10
1 2 10
  
6 6
10 20 30 40 50 60
1 2 1
2 3 1
1 3 1
1 4 6
1 5 6
4 6 2
  
3 1
10 20 30
2 3 1

Sample Output

1
2
3
Case 1: 15
Case 2: 80
Case 3: 30

Solution

首先，重要邊只有 bridge 需要維護，除了 bridge 外，不會造成任兩個點之間不連通的情況。

因此將所有 bridge 求出，建造出森林 (很多棵 tree)，接著二分最大花費，然後用貪心算法驗證答案是否可行。貪心的步驟採用先把葉節點的花費最大化，如果無法將維護成本放置到葉節點，則必然需要將維護成本交給其父節點，然後將所有葉節點移除。持續遞歸檢查。

當然可以選擇對每一個樹二分最大花費，取最大值即可。這麼寫要看當初怎麼設計，否則會挺痛苦的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
    int x, y, s;
    long long w;
    edge(int a=0, int b=0, long long c=0, int d=0):
        x(a), y(b), w(c), s(d) {}
};
vector<edge> g[32767];
int visited[32767], depth[32767], back[32767];
vector<edge> bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    back[u] = 0x3f3f3f3f;
    int sz = 1, t;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].y;
        if(v == p)	continue;
        if(!visited[v]) {
            t = findBridge(v, u, dep+1);
            sz += t;
            if(back[v] > dep)
                bridge.push_back(edge(u, v, g[u][i].w, t));
            back[u] = min(back[u], back[v]);
        } else {
            back[u] = min(back[u], depth[v]);
        }
    }
    return sz;
}
vector<edge> tree[32767];	
long long node_w[32767], place_w[32767];
int dfs(int u, long long mx_w, int p, long long p_w) {
    visited[u] = 1;
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if (visited[v] == 0) {
            if (!dfs(v, mx_w, u, tree[u][i].w))
                return 0;
        }
    }
    if (place_w[u] + p_w <= mx_w)
        place_w[u] += p_w;
    else
        place_w[p] += p_w;
    if (place_w[u] > mx_w)
        return 0;
    return 1;
        
}
int check(long long mx_w, int n) {
    for (int i = 1; i <= n; i++)
        visited[i] = 0, place_w[i] = node_w[i];
    int ok = 1;
    for (int i = 1; i <= n && ok; i++) {
        if (visited[i] == 0) {
            ok &= dfs(i, mx_w, 0, 0);
        }
    }
//	printf("check %d ok %d\n", mx_w, ok);
    return ok;
}
int main() {
    int testcase, cases = 0, n, m, x, y, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        
        long long sum = 0, low_w = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &node_w[i]);
            g[i].clear(), tree[i].clear();
            sum += node_w[i], low_w = max(low_w, node_w[i]);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(edge(x, y, w));
            g[y].push_back(edge(y, x, w));
        }
        
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                bridge.clear();
                int comp_size = findBridge(i, -1, 0);
                for (int j = 0; j < bridge.size(); j++) {
                    long long N = (long long) bridge[j].s * (comp_size - bridge[j].s);
                    tree[bridge[j].x].push_back(edge(bridge[j].x, bridge[j].y, bridge[j].w * N));
                    tree[bridge[j].y].push_back(edge(bridge[j].y, bridge[j].x, bridge[j].w * N));
                    sum += bridge[j].w * N;
//					printf("%d %d - %d\n", bridge[j].x, bridge[j].y, bridge[j].w * N);
                }
            }
        }
        
        // binary search answer
        long long l = low_w, r = sum, mid, ret;
        while (l <= r) {
            mid = (l + r)/2;
            if (check(mid, n))
                r = mid - 1, ret = mid;
            else
                l = mid + 1;
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
3
2 1
5 10
1 2 10
6 6
10 20 30 40 50 60
1 2 1
2 3 1
1 3 1
1 4 6
1 5 6
4 6 2
3 1
10 20 30
2 3 1
9999
3 3
4 5 6
1 2 1
2 3 1
3 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 12551 - Shares

Problem

現在要購買股票，每一個股票都有其花費和預期的在未來的出售價格。

但是股票採用組合包的方式進行販售，但是每一種組合包都只能購買一次，請問在資金只有 C 元的情況下，最多能在未來淨利多少。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30

Sample Output

1
2
52
2168800

Solution

每個東西只能購買一次，可見是一個 01 背包問題，但是由於 C 很大，也就是背包容量過大，導致 DP 上的困難。

但是題目並沒有特別說明測資的特殊性，後來才得知可以用 gcd 最大共同因數去降，就是縮小幣值，相當於換外國幣去思考。這麼一來 C 可以降很多，但在一般的背包問題中，gcd 的效應並不高。

把我的純真還回來啊，不想自己 yy 測資特殊性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int C, n, m;
    int x, s, q;
    int cost[512], profit[512];
    int cases = 0;
    while (scanf("%d", &C) == 1) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d %d", &cost[i], &profit[i]), profit[i] -= cost[i];
        vector< pair<int, int> > items;
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            int c = 0, p = 0;
            for (int j = 0; j < x; j++) {
                scanf("%d %d", &s, &q);
                c += cost[s] * q;
                p += profit[s] * q;
            }
            if (c <= C && p > 0)
                items.push_back(make_pair(c, p));
        }
        if (cases++)	puts("");
        if (items.size() == 0) {
            puts("0");
            continue;
        }
        if (items.size() == 1) {
            printf("%d\n", items[0].second);
            continue;
        }
        int g = C;
        for (int i = 0; i < items.size(); i++)
            g = __gcd(g, items[i].first);
        C /= g;
        for (int i = 0; i < items.size(); i++)
            items[i].first /= g;
        vector<int> dp(C + 1, 0);
        for (int i = 0; i < items.size(); i++) {
            for (int j = C; j >= items[i].first; j--)
                dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second);
        }
        printf("%d\n", dp[C]);
    }
    return 0;
}
/*
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30
*/
Read More +
解題區/解題區 - UVa

UVa 12550 - How do spiders walk on water

Problem

一個可以行走在靜止水面上的蜘蛛，現在要靠近瀑布，瀑布會於鄰近周圍會產生流速。

蜘蛛最多可以在 P 速度的水面上前進，請問最近可以靠近瀑布多少。現在已知從靜止水面靠近瀑布的部分流速，在未知的部分根據觀察是前面單位距離 1 距離 2 的線性關係。$v_{i} = a v_{i-1} + b v_{i-2}$)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 3 0 1 1 1
10 2 0 1 1 2
10 3 0 1 1 2
10 4 0 1 1 2
10 5 0 1 1 2
10 6 0 1 1 2
10 7 0 1 1 2
10 8 0 1 1 2
10 9 0 1 1 2
10 3 1 1 2 2 2 3 3 3 3 4 4
10 5 1 1 2 2 2 3 3 3 3 4 4
10 5 6 6 6 6 8 8 8 11 30 41 42
10 2 0 1 1 1 1 1 1 1 1 1 1
50 200 0 3 6 15 36

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
The spider may fall!
7
6
6
5
5
5
4
4
2
The spider may fall!
The spider is going to fall!
The spider may fall!
45

Solution

其實這題不難，在最後已知得部分解二元一次方程式即可，把未知的流速算出來，統計可以跑多遠即可。

一開始看不懂題目，以為所有流速都是線性關係，求出來的答案怪怪的。從最後已知的四個流速推測剩餘流速。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h> 
#include <algorithm>
#include <sstream> 
#include <iostream>
using namespace std;
char line[1048576];
pair<double, double> solve(double a1, double b1, double c1, double a2, double b2, double c2) {
    // a1 x + b1 y = c1, a2 x + b2 y = c2
    double dx, dy, d;
    d = a1 * b2 - b1 * a2;
    dx = c1 * b2 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return make_pair(dx / d, dy / d);
}
int main() {
    int D, P;
    while (gets(line)) {
        stringstream sin(line);
        sin >> D >> P;
        double d[32767];
        int n = 0;
        while (sin >> d[n])	n++;
        int pos = 0;
        if (n < D + 1) {
            pair<double, double> sol = solve(d[n-4], d[n-3], d[n-2], d[n-3], d[n-2], d[n-1]);
//			printf("%lf %lf\n", sol.first, sol.second);
            for (int i = n; i < D + 1; i++, n++) {
                d[i] = sol.first * d[i-2] + sol.second * d[i-1];
                if (P < d[i])	break;
            }
        }		
        for (int i = 0; i < D + 1; i++) {
            if (P < d[i])	break;
            pos++;
        }
        if (pos == D + 1)
            puts("The spider may fall!");
        else if (pos == 0)
            puts("The spider is going to fall!");
        else
            printf("%d\n", D - pos + 1);
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12094 - Battle of the Triangle

Problem

平面上有士兵和戰車，分別有 S 個、T 個，接著會有 Q 組詢問，每組詢問有三條線，每組詢問之間的線保證斜率會彼此相同 (只是移動線，這需求非常奇怪。)，請問三條線拉出的 7 個區域中，中間與外側三塊地士兵、戰車個數差異為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
8 5 2
-1 8
-7 3
-2 1
-2 -1
-5 -2
6 -1
2 -4
-4 -5
1 7
1 1
3 4
-6 5
-12 -6
2 -2 10
-2 6 6
-5 -3 1
1 -1 5
1 -3 -3
5 3 -15
0 0 0

Sample Output

1
2
3
Battle Field 1:
Query 1: 1 -2
Query 2: 1 -1

Solution

先獲得需要劃分的斜率，對三種斜率進行點的排序，因此對得到六個排序結果 (士兵和戰車)。之後就能在排序結果中，二分搜尋該線的左側、右側分別有多少點。

解決這個之後，要來看看噁心的排容原理，這裡還是建議參照 flere 的圖示：

對於拉出的三角形三個交點編號 A, B, C，接著對其做區域編號，

(1) BC 線段的左邊 有區域 1 2 3 6
(2) AC 線段的左邊 有區域 2 6 7
(3) AB 線段的下面 有區域 2 3 4
(1) - (2) - (3) 就可以得到區域 1 - 2 - 7 - 4
就是我們要的答案

flere

在程式邏輯上，挑一點與其一線同側，另兩條線與點異側。

沒有辦法單獨對區域內部搜尋點個數，然後統計完再相減，即使使用 range query，也無法在有效時間內完成任意三角形的範圍搜索 (矩形可以考慮，用等腰直角三角形也好。)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define eps 1e-6
const double pi = acos(-1); 
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator*(const double &a) const {
        return Pt(x * a, y * a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.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);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
struct Line {
    int A, B, C;
    bool operator<(const Line &a) const {
        double t1 = atan2(B, A);
        double t2 = atan2(a.B, a.A);
        if (t1 < 0)	t1 += pi;
        if (t2 < 0)	t2 += pi;
        return t1 < t2;
    }
};
Pt getIntersection(Line l1, Line l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.A, b1 = l1.B, c1 = -l1.C;
    a2 = l2.A, b2 = l2.B, c2 = -l2.C;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
struct cmp {
    static Line base;
    bool operator() (const Pt &p1, const Pt &p2) const {
        double c1, c2;
        c1 = p1.x * base.A + p1.y * base.B;
        c2 = p2.x * base.A + p2.y * base.B;
        if (fabs(c1 - c2) > eps)
            return c1 < c2;
        return false;
    }
};
Line cmp::base;
int main() {
    int cases = 0;
    int n, m, q;
    double x, y;
    while (scanf("%d %d %d", &n, &m, &q) == 3 && n) {
        vector<Pt> soldiers, tanks;
        vector<Pt> soldier[3], tank[3];
        Line Q[10000][3];
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            soldiers.push_back(Pt(x, y));
        }
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            tanks.push_back(Pt(x, y));
        }
        for (int i = 0; i < q; i++) {
            for (int j = 0; j < 3; j++) {
                scanf("%d %d %d", &Q[i][j].A, &Q[i][j].B, &Q[i][j].C);
                if (Q[i][j].A < 0 || (Q[i][j].A == 0 && Q[i][j].B < 0)) {
                    Q[i][j].A = -Q[i][j].A;
                    Q[i][j].B = -Q[i][j].B;
                    Q[i][j].C = -Q[i][j].C;
                }
            }
            sort(Q[i], Q[i] + 3);
        }
        for (int i = 0; i < 3; i++) {
            soldier[i] = soldiers;
            tank[i] = tanks;
            cmp::base = Q[0][i];
            sort(soldier[i].begin(), soldier[i].end(), cmp());
            sort(tank[i].begin(), tank[i].end(), cmp());
        }
//		for (int i = 0; i < 3; i++) {
//			for (int j = 0; j < soldier[i].size(); j++)
//				printf("%.2lf %.2lf ,", soldier[i][j].x, soldier[i][j].y);
//			puts("\n--++--");
//		}
        printf("Battle Field %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
//			for (int j = 0; j < 3; j++)
//				printf("%d %d %d -\n", Q[i][j].A, Q[i][j].B, Q[i][j].C);
            Pt pabc[3];
            pabc[0] = getIntersection(Q[i][1], Q[i][2]); // bc
            pabc[1] = getIntersection(Q[i][0], Q[i][2]); // ac
            pabc[2] = getIntersection(Q[i][0], Q[i][1]); // ab
            int ret1 = 0, ret2 = 0;
            int tmp[3];
            for (int j = 0; j < 3; j++) {
                cmp::base = Q[i][j];
                tmp[j] = (int)(lower_bound(soldier[j].begin(), soldier[j].end(), 
                pabc[(j+1)%3], cmp()) - soldier[j].begin());
                int v1 = (Q[i][j].A * pabc[j].x + Q[i][j].B * pabc[j].y + Q[i][j].C < 0);
                int v2 = (Q[i][j].A * soldier[j][0].x + Q[i][j].B * soldier[j][0].y + Q[i][j].C < 0);
                int v3 = (Q[i][j].A * soldier[j][soldier[j].size()-1].x + Q[i][j].B * soldier[j][soldier[j].size()-1].y + Q[i][j].C < 0);
                    
                if (j == 0)  {
                    if (tmp[j]) {
                        if (v1 != v2)
                            tmp[j] = soldier[j].size() - tmp[j];
                    } else {
                        if (v1 == v3)
                            tmp[j] = soldier[j].size() - tmp[j];
                    }
                } else {
                    if (tmp[j]) {
                        if (v1 == v2)
                            tmp[j] = soldier[j].size() - tmp[j];
                    } else {
                        if (v1 != v3)
                            tmp[j] = soldier[j].size() - tmp[j];
                    }
                }
//				printf("[%d] soldier %d\n", j, tmp[j]);
            }
            ret1 = tmp[0] - tmp[1] - tmp[2];
            for (int j = 0; j < 3; j++) {
                cmp::base = Q[i][j];
                tmp[j] = (int)(lower_bound(tank[j].begin(), tank[j].end(), 
                pabc[(j+1)%3], cmp()) - tank[j].begin());
                int v1 = (Q[i][j].A * pabc[j].x + Q[i][j].B * pabc[j].y + Q[i][j].C < 0);
                int v2 = (Q[i][j].A * tank[j][0].x + Q[i][j].B * tank[j][0].y + Q[i][j].C < 0);
                int v3 = (Q[i][j].A * tank[j][tank[j].size()-1].x + Q[i][j].B * tank[j][tank[j].size()-1].y + Q[i][j].C < 0);
                    
                if (j == 0)  {
                    if (tmp[j]) {
                        if (v1 != v2)
                            tmp[j] = tank[j].size() - tmp[j];
                    } else {
                        if (v1 == v3)
                            tmp[j] = tank[j].size() - tmp[j];
                    }
                } else {
                    if (tmp[j]) {
                        if (v1 == v2)
                            tmp[j] = tank[j].size() - tmp[j];
                    } else {
                        if (v1 != v3)
                            tmp[j] = tank[j].size() - tmp[j];
                    }
                }
//				printf("[%d] tank %d\n", j, tmp[j]);
            }
            ret2 = tmp[0] - tmp[1] - tmp[2];
            printf("Query %d: %d %d\n", i+1, ret1, ret2);
        }
    }
    return 0;
}
/*
8 5 2
-1 8
-7 3
-2 1
-2 -1
-5 -2
6 -1
2 -4
-4 -5
1 7
1 1
3 4
-6 5
-12 -6
2 -2 10
-2 6 6
-5 -3 1
1 -1 5
1 -3 -3
5 3 -15
0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 11600 - Masud Rana

Problem

給 N 個城市，城市之間會有 M 條當前的安全邊，在其餘邊皆有邪惡組織出現，來阻擋城市之間的運行。

現在人在編號 1，每次將隨機挑任何相鄰的城市走過去 (隔天又會再挑一個鄰近的城市)，如果走過去的路上遇到邪惡組織則會將其殲滅，請問期望值需要幾天才能將 N 個城市彼此之間都存有連通路徑。

Sample Input

1
2
3
4
5
2
3 1
2 3
4 1
2 3

Sample Output

1
2
Case 1: 1.000000
Case 2: 3.500000

Solution

特別小心輸出的誤差要在 1e-6，以為只需要輸出 1 位，結果一直 WA。

事實上，將狀態壓縮成每一個連通元件的節點個數，對於連通元件之間做拉邊即可。

對於狀態 u, v，期望值 E[u] = 1 + E[v] p + E[u] q，

E[v] * p 表示：將兩個不同連通元件之間拉邊，則會將兩個連通元件融合，機率 p。
E[u] * q 表示：在各自的連通元件內布拉邊，不影響狀態結果。

左移一下得到 E[u] = (1 + E[v] * p) / (1 - q);

這一題必須考慮現在位於哪個連通元件，所以特別標記狀態的第一個連通元件為當前所在位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// similar 1390 - Interconnect
int parent[32], weight[32];
int findp(int x) {
    return parent[x] == x ? x : findp(parent[x]);
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return;
    if (weight[x] > weight[y])
        parent[y] = x, weight[x] += weight[y];
    else
        parent[x] = y, weight[y] += weight[x];
}
#define hash_mod 1000003
struct state {
    vector<int> c;
    unsigned int hash() {
        unsigned int a = 63689, b = 378551;
        unsigned int value = 0;
        for (int i = 0; i < c.size(); i++) {
            value = value * a + c[i];
            a *= b;
        }
        return value % hash_mod;
    }
    bool operator<(const state &a) const {
        if (c.size() != a.c.size())
            return c.size() < a.c.size();
        for (int i = 0; i < c.size(); i++)
            if (c[i] != a.c[i])
                return c[i] < a.c[i];
        return false;
    }
};
map<state, double> hash[hash_mod];
double dfs(state &u) {
    if (u.c.size() == 1)	return 0;
    sort(u.c.begin() + 1, u.c.end());
    int h = u.hash();
    if (hash[h].find(u) != hash[h].end())
        return hash[h][u];
    double &ret = hash[h][u];
    double self = 0, total = 0;
    ret = 0;
    for (int i = 0; i < u.c.size(); i++)
        total += u.c[i];
    total = total - 1, self = u.c[0] - 1;
    for (int i = 1; i < u.c.size(); i++) {
        state v = u;
        v.c[0] += v.c[i];
        v.c.erase(v.c.begin() + i);
        ret += u.c[i] * dfs(v);
    }
    // E[u] = 1 + E[v] * p + E[u] * q
    ret = (ret / total) + 1;
    ret = ret / (1 - self / total);
    return ret;
}
int main() {
    int n, m, x, y;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            parent[i] = i, weight[i] = 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            joint(x, y);
        }
        
        state st;
        
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i && parent[i] == findp(1))
                st.c.push_back(weight[i]);
        } 
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i && parent[i] != findp(1)) // root
                st.c.push_back(weight[i]);
        }
        printf("Case %d: %lf\n", ++cases, dfs(st));
    }
    return 0;
}
/*
2
3 1
2 3
4 1
2 3
9999
3 3
1 2
2 3
3 1
*/
Read More +
解題區/解題區 - UVa

UVa 11529 - Strange Tax Calculation

Problem

任挑三個點拉出三角形，三角形內部的點數期望值為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
29 84
81 81
28 36
60 40
85 38
5
0 0
10 0
0 10
10 10
6 7
0

Sample Output

1
2
City 1: 0.20
City 2: 0.20

Solution

反過來寫，這一點會被多少個三角形包含住。

為了要計算這一個點 P 被多少三角形包含住，把這個點 P 當作基礎點，對其他點做極角排序。排序完套用極角掃描線算法，對於當前線上的點 Q，往回追溯 180 度內，任挑兩個點與其並成三角形，保證不包含 P。

那麼要得到包含 P 的就反過來用全部組合扣到不包含的結果。

因為要窮舉每一點做極角排序，作法會在 O(n^2 log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-9
const double pi = acos(-1);
struct Pt {
    double x, y;
    double angle;
    Pt(double a = 0, double b = 0):x(a), y(b) {
        angle = atan2(b, a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(angle - a.angle) > eps)
            return angle < a.angle;
        return false;
    }
}; 
long long C[1300][1300] = {};
long long getContainTriangle(int st, Pt D[], int n) {
    static Pt A[4096];
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i == st)	continue;
        A[m++] = Pt(D[i].x - D[st].x, D[i].y - D[st].y);
    }
    sort(A, A + m);
    for (int i = 0; i < m; i++)
        A[i + m] = A[i], A[i+m].angle += 2 * pi;
    long long ret = 0;
    for (int i = 0, j = 1; i < m; i++) { // point(i, ?, ?)
        while (A[j].angle - A[i].angle <= pi - eps)	j++;
        ret += C[j - i - 1][2];
    }
    return C[m][3] - ret;
}
int main() {
    C[0][0] = 1;
    for (int i = 0; i < 1205; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    int n, cases = 0;
    Pt D[1500];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) 
            scanf("%lf %lf", &D[i].x, &D[i].y);
        long long contain = 0;// contain
        for (int i = 0; i < n; i++)
            contain += getContainTriangle(i, D, n); // with i-th point.
        printf("City %d: %.2lf\n", ++cases, (double)contain / C[n][3]);
    }
    return 0;
}
/*
5
29 84
81 81
28 36
60 40
85 38
5
0 0
10 0
0 10
10 10
6 7
0
*/
Read More +
解題區/解題區 - UVa

UVa 1331 - Minimax Triangulation

Problem

將一個簡單多邊形三角化，並且讓最大面積的三角形越小越好。

Sample Input

1
2
3
4
5
6
7
8
1
6
7 0
6 2
9 5
3 5
0 3
1 1

Sample Output

1
9.0

Solution

矩陣鏈乘積的方式著手 dp。

在此必須檢查劃分兩區間的三角形中內部不包含任何點，這裡利用外積 cross 進行計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    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);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    bool operator==(const Pt &a) const {
    	return (fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
struct Seg {
    Pt s, e;
    Seg(Pt a = Pt(), Pt b = Pt()):
        s(a), e(b) {}
};
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;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double ptToSeg(Seg seg, Pt p) {
    double c = 1e+30;
    if(between(seg.s, seg.e, p))
        c = min(c, distProjection(seg.s, seg.e, p));
    else
        c = min(c, min(dist(seg.s, p), dist(seg.e, p)));
    return c;
}
double getArea(Pt a, Pt b, Pt c) {
    return fabs(cross(a, b, c))/2.0;
}
int isEmptyTriangle(Pt a, Pt b, Pt c, Pt D[], int n) {
    for (int i = 0; i < n; i++) {
        if (D[i] == a || D[i] == b || D[i] == c)
            continue;
        if (cross(a, D[i], b) * cross(a, D[i], c) < 0 && 
            cross(b, D[i], a) * cross(b, D[i], c) < 0 &&
            cross(c, D[i], a) * cross(c, D[i], b) < 0)
            return 0;
    }
    return 1;
}
int main() {
    int testcase, n;
    Pt D[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            D[i].read();
        for (int i = 0; i < n; i++)
            D[i + n] = D[i];
        double dp[128][128];
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                dp[i][j] = 1e+30;
            }
            dp[i][i] = dp[i][i+1] = 0;
        }
        double ret = 1e+30;
        for (int i = 2; i < n; i++) {
            for (int j = 0; j < n; j++) {// [j, j+i]
                int l = j, r = j + i;
                double &v = dp[l][r];
                for (int k = l+1; k < r; k++) {
                    if (isEmptyTriangle(D[l], D[r], D[k], D, n))
                        v = min(v, max(max(dp[l][k], dp[k][r]), getArea(D[l], D[r], D[k])));
                }
            }
        }
        for (int i = 0; i < n; i++)
            ret = min(ret, dp[i][i + n - 1]);
        printf("%.1lf\n", ret);
    }
    return 0;
}
/*
1
6
7 0
6 2
9 5
3 5
0 3
1 1
*/
Read More +