ACM/ICPC 2011 北京现场赛 Hou Yi’s Secret 题解
这是一道阴险的水题。现场赛的时候是队长 Wideas 过的，似乎过得也没有太大障碍。但是赛后我自己写，感觉题意比较模糊。如果没有看样例测试数据，可能怎么错的都不知道。
主要注意的有几点，一个是，在某处如果射了 2 箭，其实只会产生一个洞，所以重复给出的点只能算一个；还有一点，如果所有三角形的集合是 A, 以“相似关系”划分这个集合，即有 A = A1 ∪ A2 ∪ … ∪ An, 其中集合 Ai 中的三角形互相相似，那么题目要求的东西是 max { |Ai| }.
代码如下：
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 | #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const double eps = 1e-9; inline int sgn(double a) { return a > eps ? 1 : a < -eps ? -1 : 0; } inline bool eq(double a, double b) { return sgn(b - a) == 0; } inline bool eq(double a, double b, double c) { return eq(a, b) && eq(b, c) && eq(a, c); } struct point { int x, y; inline point() { } inline point(const int x, const int y) : x(x), y(y) { } inline bool operator<(const point &b) const { if (x == b.x) return y < b.y; return x < b.x; } inline bool operator==(const point &b) const { return x == b.x && y == b.y; } inline point operator-(const point &b) const { return point(x - b.x, y - b.y); } inline int magsqr() const { return x * x + y * y; } inline double mag() const { return sqrt((double)magsqr()); } }; struct triangle { point a, b, c; double x, y, z; inline triangle() { } inline triangle(const point &a, const point &b, const point &c) : a(a), b(b), c(c) { sort((point *)&a, (point *)&a + 3); x = (a - b).mag(); y = (b - c).mag(); z = (c - a).mag(); sort((double *)&x, (double *)&x + 3); } inline bool is_valid() const { if (x + y <= z || y + z <= x || z + x <= y) return false; point u = b - a, v = c - b; if (u.x * v.y == u.y * v.x) return false; return true; } }; inline bool is_similar(const triangle &u, const triangle &v) { return eq(u.x / v.x, u.y / v.y, u.z / v.z); } point pts[100]; int npt; triangle tris[10000]; int ntri; inline void build_triangles() { ntri = 0; for (int i = 0; i < npt; ++i) { for (int j = i + 1; j < npt; ++j) { for (int k = j + 1; k < npt; ++k) { triangle tri(pts[i], pts[j], pts[k]); if (tri.is_valid()) tris[ntri++] = tri; } } } } inline int count_triangles() { int max_similar = 0; for (int i = 0; i < ntri; ++i) { int similar = 0; for (int j = i; j < ntri; ++j) similar += is_similar(tris[i], tris[j]) ? 1 : 0; max_similar = max(max_similar, similar); } return max_similar; } int main() { // freopen("input.txt", "r", stdin); while (scanf("%d", &npt)) { if (npt == 0) break; for (int i = 0; i < npt; ++i) scanf("%d %d", &pts[i].x, &pts[i].y); sort(pts, pts + npt); npt = unique(pts, pts + npt) - pts; build_triangles(); printf("%d\n", count_triangles()); } return 0; } |
