ACM/ICPC Northwestern Europe 2007 解题报告

这套题比较。。。有意思。。。

Assemble
据说是简单题

March of the Penguins
你看相传每个ice floes是有跳的次数限制的是吧。。。用经典的拆点流量限制法，每个ice floes拆成i和i'，i到i'的流量上限为跳的次数，然后如果能从i跳到j连一条i'到j的边(流量无穷大)。。。点数好像有点多。。。不要客气～，dinic很快的～

Containers
推一下式子，在实数意义下可以求最值是吧。然后现在限制整数。。。上下浮动一下吧。。。

Youth Hostel Dorm
相当麻烦的状态压缩dp，还么写。。。

Escape from Enemy Territory
二分 +  bfs应该可以，或者排个序 + 并查集

Flight Safety
比 较麻烦的计算几何题。大体的想法是二分答案 + judge。得知了答案r以后我们可以把整个多边形往外膨胀r个单位然后判断是否整条路线都在里面。具体实现的时候我们把整个图形拆成原来的多边形，一堆 矩形（每天边对应一个矩形）和一堆圆（每个点对应一个圆），每一部分求一下航线有哪些部分在里面，最后判断是否整条航线都被包含了。。。
CODE
  1//    Northwestern Europe 2007, Flight Safety
  2//    Written By FreePeter
  3
  4#include <cstdio>
  5#include <cstring>
  6#include <iostream>
  7#include <cmath>
  8#include <vector>
  9#include <algorithm>
 10
 11using namespace std;
 12
 13const double eps = 1e-8;
 14struct Point {
 15    double x, y;
 16    Point() {}
 17    Point(double _x, double _y) : x(_x), y(_y) {}
 18    bool operator<(const Point &p) const {
 19        if (fabs(x - p.x) > eps) return x < p.x;
 20        else return y < p.y;
 21    }
 22    double length_to(const Point &p) const {
 23        return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
 24    }
 25}oo(223456789.0, 897654321.0);
 26
 27double point_segment(const Point &p0, const Point &p1, const Point &p2);
 28void adjust_len(double len, double &x, double &y);
 29bool inside_segment(const Point &p0, const Point &p1, const Point &p2);
 30bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p);
 31bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d);
 32double cross(const Point &p0, const Point &p1, const Point &p2);
 33
 34struct Shape {
 35    virtual bool inside(const Point &x) = 0;
 36    virtual void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) = 0;
 37};
 38struct Circle : Shape {
 39    Point o;
 40    double r;
 41    bool inside(const Point &x) {
 42        return o.length_to(x) < r + eps;
 43    }
 44    void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) {
 45        if (inside(p0) && inside(p1)) {
 46            lst.push_back(make_pair(p0, p1));
 47            return;
 48        }
 49
 50        double dist = point_segment(o, p0, p1);
 51        if (dist + eps > r) return;
 52        
 53        double dx = -(p1.y - p0.y), dy = (p1.x - p0.x);
 54        adjust_len(dist, dx, dy);
 55        Point mid(o.x + dx, o.y + dy);
 56        
 57        if (fabs(cross(p0, p1, mid)) > eps) 
 58            mid = Point(o.x - dx, o.y - dy);
 59
 60        dx = p1.x - p0.x; dy = p1.y - p0.y;
 61        adjust_len(sqrt(r * r - dist * dist), dx, dy);
 62        Point t1(mid.x + dx, mid.y + dy), t2(mid.x - dx, mid.y - dy);
 63
 64        bool in1 = inside_segment(t1, p0, p1), in2 = inside_segment(t2, p0, p1);
 65        if (in1 && in2) lst.push_back(make_pair(t1, t2));
 66        else if (in1 && (!in2)) lst.push_back(make_pair(p0, t1));
 67        else if (in2 && (!in1)) lst.push_back(make_pair(t2, p1));
 68    }
 69};
 70struct Polygon : Shape {
 71    int n;
 72    Point p[40];
 73    bool inside(const Point &x) {
 74        int cnt = 0;
 75        for (int i = 0; i < n; ++i)
 76            if (seg_cross(x, oo, p[i], p[i + 1])) ++cnt;
 77        return cnt % 2;
 78    }
 79    void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) {
 80        vector<Point> x;
 81        x.push_back(p0); x.push_back(p1);
 82        for (int i = 0; i < n; ++i) {
 83            Point tmp;
 84            if (seg_cross(p0, p1, p[i], p[i + 1], tmp)) {
 85                x.push_back(tmp);
 86            }
 87        }
 88
 89        sort(x.begin(), x.end());
 90        for (int i = 0; i + 1 < x.size(); ++i) {
 91            Point mid((x[i].x + x[i + 1].x) / 2.0, (x[i].y + x[i + 1].y) / 2.0);
 92            if (inside(mid)) 
 93                lst.push_back(make_pair(x[i], x[i + 1]));
 94        }
 95
 96    }
 97};
 98
 99Polygon poly[30];
100Circle cir[30][30];
101Polygon rect[30][30];
102Point route[30];
103int c, n;
104
105void init();
106void work();
107bool judge_valid(double r);
108bool xy_cmp(double x0, double x1, double x2);
109int sgn(double x);
110
111int main() {
112    int t;
113    cin >> t;
114    for (; t > 0; --t) {
115        init();
116        work();
117    }
118    return 0;
119}
120
121void init() {
122    cin >> c >> n;
123    for (int i = 0; i < n; ++i)
124        cin >> route[i].x >> route[i].y;
125
126    for (int i = 0; i < c; ++i) {
127        cin >> poly[i].n;
128        for (int j = 0; j < poly[i].n; ++j)
129            cin >> poly[i].p[j].x >> poly[i].p[j].y;
130        poly[i].p[poly[i].n] = poly[i].p[0];
131    }
132}    
133
134void work() {
135    const double Accurate = 1e-4;
136    double h = 0.0, t = 30000.0, mid = (h + t) / 2.0;
137    for (; h + Accurate < t; mid = (h + t) / 2.0) {
138        if (judge_valid(mid)) t = mid;
139        else h = mid;
140    }
141
142    printf("%.15lf\n", mid);
143}
144
145
146double point_segment(const Point &p0, const Point &p1, const Point &p2) {
147    return cross(p0, p1, p2) / p1.length_to(p2);
148}
149
150void adjust_len(double len, double &x, double &y) {
151    double ratio = len / sqrt(x * x + y * y);
152    x *= ratio; y *= ratio;
153}
154
155bool inside_segment(const Point &p0, const Point &p1, const Point &p2) {
156    if (fabs(p2.x - p1.x) > fabs(p2.y - p1.y))
157        return xy_cmp(p0.x, p1.x, p2.x);
158    else 
159        return xy_cmp(p0.y, p1.y, p2.y);
160}
161
162bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p) {
163    double s1 = cross(a, b, c), s2 = cross(a, b, d), s3 = cross(c, d, a), s4 = cross(c, d, b);
164    int d1 = sgn(s1), d2 = sgn(s2), d3 = sgn(s3), d4 = sgn(s4);
165    
166    if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) {
167        p.x = (c.x * s2 - d.x * s1) / (s2 - s1);
168        p.y = (c.y * s2 - d.y * s1) / (s2 - s1);
169        return true;
170    }
171    
172    return false;
173}
174    
175bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d) {
176    double s1 = cross(a, b, c), s2 = cross(a, b, d), s3 = cross(c, d, a), s4 = cross(c, d, b);
177    int d1 = sgn(s1), d2 = sgn(s2), d3 = sgn(s3), d4 = sgn(s4);
178    
179    return ((d1 ^ d2) == -2 && (d3 ^ d4) == -2);
180}    
181
182double cross(const Point &p0, const Point &p1, const Point &p2) {
183    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
184}
185
186bool judge_valid(double r) {
187    //    Initialize rectangles & circles
188    for (int i = 0; i < c; ++i) {
189        for (int j = 0; j < poly[i].n; ++j) { 
190            Point &p0 = poly[i].p[j], &p1 = poly[i].p[j + 1];
191            double dx = -(p1.y - p0.y), dy = p1.x - p0.x;
192            adjust_len(r, dx, dy);
193
194            rect[i][j].n = 4;
195            rect[i][j].p[0] = Point(p0.x + dx, p0.y + dy);
196            rect[i][j].p[1] = Point(p0.x - dx, p0.y - dy);
197            rect[i][j].p[2] = Point(p1.x - dx, p1.y - dy);
198            rect[i][j].p[3] = Point(p1.x + dx, p1.y + dy);
199            rect[i][j].p[4] = rect[i][j].p[0];
200
201            cir[i][j].o = poly[i].p[j];
202            cir[i][j].r = r;
203        }
204    }
205
206
207
208    //    Judge all the segments
209    for (int i = 0; i < n - 1; ++i) {
210        vector<pair<Point, Point> > lst;
211        for (int j = 0; j < c; ++j) {
212            poly[j].append_segment(route[i], route[i + 1], lst);
213            for (int k = 0; k < poly[j].n; ++k) {
214                rect[j][k].append_segment(route[i], route[i + 1], lst);
215                cir[j][k].append_segment(route[i], route[i + 1], lst);
216            }
217    
218        }
219
220        static pair<double, double> tmp[10000];
221        int tmp_cnt = 0;
222        double b;
223
224        if (fabs(route[i].x - route[i + 1].x) > fabs(route[i].y - route[i + 1].y)) {
225            b = fabs(route[i + 1].x - route[i].x);
226            for (vector<pair<Point, Point> >::iterator it = lst.begin(); it != lst.end(); ++it) {
227                tmp[tmp_cnt].first = fabs(it->first.x - route[i].x);
228                tmp[tmp_cnt].second = fabs(it->second.x - route[i].x);
229                ++tmp_cnt;
230            }
231        }
232        else {
233            b = fabs(route[i + 1].y - route[i].y);
234            for (vector<pair<Point, Point> >::iterator it = lst.begin(); it != lst.end(); ++it) {
235                tmp[tmp_cnt].first = fabs(it->first.y - route[i].y);
236                tmp[tmp_cnt].second = fabs(it->second.y - route[i].y);
237                ++tmp_cnt;
238            }
239        }
240    
241
242        //    Whether the segment is covered
243        for (int j = 0; j < tmp_cnt; ++j)
244            if (tmp[j].first > tmp[j].second) swap(tmp[j].first, tmp[j].second);
245        sort(tmp, tmp + tmp_cnt);
246        if (tmp[0].first > eps) return false;
247        double tail = tmp[0].second;
248        for (int j = 1; j < tmp_cnt; ++j) {
249            if (tail + eps < tmp[j].first) return false;
250            tail >?= tmp[j].second;
251            if (tail + eps > b) break;
252        }
253        if (tail + eps < b) return false;
254
255    }
256
257        
258    return true;
259}
260
261bool xy_cmp(double x0, double x1, double x2) {
262    if (x1 < x2) 
263        return (x1 < x0 + eps && x0 < x2 + eps);
264    else 
265        return (x2 < x0 + eps && x0 < x1 + eps);
266}
267
268int sgn(double x) {
269    return x > eps ? 1 : (x < -eps ? -1 : 0);
270}
271
272
273

Summits
一道比较经典的思路题了，大体就是按照高度从高往低处理，每次合并当前高度和它周围的比它低的。最后判断每一块中能达到的最高的。
注意我合并的时候使用树形并查集，并且严格保证把低的合并到高的。。。处理的要自仔细考虑细节。
CODE
  1//    Northwestern Europe 2007, Summits
  2//    Written By FreePeter
  3
  4#include <cstdio>
  5#include <cstring>
  6#include <iostream>
  7#include <vector>
  8#include <algorithm>
  9
 10using namespace std;
 11
 12const int MaxN = 500 + 10;
 13const int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
 14int s[MaxN * MaxN];
 15int h, w, diff_h[MaxN * MaxN], diff_h_cnt;
 16vector<int> grid_of_h[MaxN * MaxN];
 17int father[MaxN * MaxN], ans;
 18int delta;
 19
 20void init();
 21void work();
 22int find_root(int u);
 23void unite(int u, int v);
 24bool is_valid(int x, int y);
 25void check_height(int id);
 26
 27int main() {
 28    int t;
 29    scanf("%d", &t);
 30    for (; t > 0; --t) {
 31        init();
 32        work();
 33    }
 34    return 0;
 35}
 36
 37void init() {
 38    scanf("%d%d%d", &h, &w, &delta);
 39
 40    diff_h_cnt = 0;
 41    for (int i = 0; i < h; ++i)
 42        for (int j = 0; j < w; ++j) {
 43            scanf("%d", &s[i * w + j]);
 44            diff_h[diff_h_cnt++] = s[i * w + j];
 45        
 46        }
 47    
 48    sort(diff_h, diff_h + diff_h_cnt);
 49    diff_h_cnt = unique(diff_h, diff_h + diff_h_cnt) - diff_h;
 50    
 51    for (int i = 0; i < diff_h_cnt; ++i)
 52        grid_of_h[i].clear();
 53    for (int i = 0; i < h; ++i)
 54        for (int j = 0; j < w; ++j) {
 55            grid_of_h[lower_bound(diff_h, diff_h + diff_h_cnt, s[i * w + j]) - diff_h].push_back(i * w + j);
 56        }
 57
 58}
 59
 60void work() {
 61    for (int i = 0; i < w * h; ++i)
 62        father[i] = i;
 63
 64    ans = w * h;
 65    int p = diff_h_cnt - 1;
 66
 67    for (int i = diff_h_cnt - 1; i >= 0; --i) {
 68        for (vector<int>::iterator it = grid_of_h[i].begin(); it != grid_of_h[i].end(); ++it) {
 69            int x = *it / w, y = *it % w;
 70            for (int d = 0; d < 4; ++d) {
 71                int nx = x + dx[d], ny = y + dy[d];
 72                if (is_valid(nx, ny) && s[nx * w + ny] >= s[x * w + y]) {
 73                    unite(find_root(nx * w + ny), find_root(x * w + y));
 74                }
 75            }
 76        }
 77    
 78        for (; diff_h[p] >= diff_h[i] + delta; --p) {
 79            continue;
 80        }
 81        if (i == 0) continue;
 82        
 83        for (; p >= 0 && diff_h[p] >= diff_h[i - 1] + delta; --p) {
 84            check_height(p);
 85        }
 86
 87    }
 88
 89    for (; p >= 0; --p)
 90        check_height(p);
 91
 92    cout << ans << endl;
 93}
 94
 95int find_root(int u) {
 96    int q = u;
 97    for (; q != father[q]; )
 98        q = father[q];
 99    for (; u != father[u]; ) {
100        int tmp = father[u];
101        father[u] = q;
102        u = tmp;
103    }
104    return q;
105}
106
107void unite(int u, int v) {
108    if (s[u] < s[v]) father[u] = v;
109    else father[v] = u;
110}
111
112bool is_valid(int x, int y) {
113    return x >= 0 && x < h && y >= 0 && y < w;
114}
115
116void check_height(int id) {
117    for (vector<int>::iterator it = grid_of_h[id].begin(); it != grid_of_h[id].end(); ++it)
118        if (s[find_root(*it)] > s[*it]) {
119            --ans;
120        }
121}
122
123
124
125
126

Obfuscation
字典树 + dp

Tower Parking
简单的模拟题

Walk
非常有趣的一道题。
首先我们在两点拉一条线，观察每一个封闭等高线被经过的次数。
如果某条等高线被经过偶数次，那么两点同在线内或线外，必然有办法不经过这条线。
如果经过奇数次，那么在不同侧，必须要经过一次，并且总可以有办法只经过一次。
接下来要确定经过等高线的次序。基本想法是这个顺序是唯一的，我是以最左边交到的点作为次序来排的。。。
另外关于刚好交在端点的情况需要考虑下。。。
CODE
 1//    Northwestern Europe 2007, Walk
 2//    Written By FreePeter
 3
 4#include <cstdio>
 5#include <cstring>
 6#include <iostream>
 7#include <vector>
 8#include <cmath>
 9#include <algorithm>
10
11using namespace std;
12
13struct Point {
14    double x, y;
15};
16const int MaxN = 3000 + 100;
17const double eps = 1e-8;
18vector<Point> poly[MaxN];
19int h[MaxN];
20int n, intersect_cnt[MaxN];
21double left_most[MaxN];
22
23void init();
24void work();
25bool my_cmp(int a, int b) {
26    return left_most[a] < left_most[b];
27}
28
29int main() {
30
31    //freopen("in.txt", "r", stdin);
32
33    int t;
34    scanf("%d", &t);
35    for (; t > 0; --t) {
36        init();
37        work();
38    }
39
40    return 0;
41}
42
43void init() {
44    scanf("%d", &n);
45    for (int i = 0; i < n; ++i) {
46        scanf("%d", &h[i]);
47        int pn;
48        scanf("%d", &pn);
49        poly[i].resize(pn + 1);
50        for (int j = 0; j < pn; ++j) {
51            scanf("%lf%lf", &poly[i][j].x, &poly[i][j].y);
52        }
53        poly[i][pn] = poly[i][0];
54                    
55    }
56}    
57
58void work() {
59    fill(intersect_cnt, intersect_cnt + n, 0);
60    fill(left_most, left_most + n, 1e100);
61    
62    for (int i = 0; i < n; ++i) {
63        for (int j = 0; j + 1 < poly[i].size(); ++j) {
64            double x1 = poly[i][j].x, y1 = poly[i][j].y, x2 = poly[i][j + 1].x, y2 = poly[i][j + 1].y;
65            if (fabs(y1 - y2) < eps) continue;
66            if (y1 > y2) {
67                swap(x1, x2); swap(y1, y2);
68            }
69            double y = 0.0;
70            if (!(y1 < y + eps && y + eps < y2)) continue;
71            double x = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
72            if (x < 0.0 || x > 100000.0) continue;
73
74            ++intersect_cnt[i];
75            left_most[i] <?= x;
76        }
77    }
78
79    int seq[MaxN];
80    for (int i = 0; i < n; ++i) seq[i] = i;
81    sort(seq, seq + n, my_cmp);
82    int pre_h = -1;
83    int up_cnt = 0, down_cnt = 0;
84    for (int i = 0; i < n; ++i) {
85        if (intersect_cnt[seq[i]] % 2 == 0) continue;
86        if (pre_h == h[seq[i]]) continue;
87        if (pre_h != -1)
88            if (pre_h < h[seq[i]]) up_cnt += h[seq[i]] - pre_h;
89            else down_cnt += pre_h - h[seq[i]];
90        pre_h = h[seq[i]];
91    }    
92    
93    printf("%d %d\n", up_cnt, down_cnt);
94}
95

Comments

Article rating:
Your rating:

Categories

Based on community consensus.

Activity for this knol

This week:

21pageviews

Totals:

598pageviews
©2009 Google