首页 > 代码库 > BZOJ2338 [HNOI2011]数矩形
BZOJ2338 [HNOI2011]数矩形
恩。。。什么神题，表示不会。。。
然后各种乱搞，发现最坏都是O(n ^ 4)的复杂度：
做法即暴力，求出所有对角线
查看那些能构成矩形的对角线，即长度和中点都相同的线段，算一下面积即可。
后来看了看各种题解，都是这么做的。。。真的不会被卡嘛= =
蒟蒻也只好这么乱搞了
话说貌似想到了一种O(n ^ 2 * log(n ^ 2))的做法？
就是线段排好序以后，查看那些长度和中点都相同的的对角线，按照极角排序
由凸包旋转卡壳的思想，去除排序复杂度，是可以做到O（线段个数）的。
好烦。。。不想写的说>_<
1 /************************************************************** 2 Problem: 2338 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1808 ms 7 Memory:36224 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 #define P Point 14 #define L Line 15 using namespace std; 16 typedef long long ll; 17 const int N = 1505; 18 const int M = N * N >> 1; 19 20 int n, tot; 21 ll ans; 22 23 struct Point { 24 ll x, y; 25 P() {} 26 P(ll _x, ll _y) : x(_x), y(_y) {} 27 28 inline bool operator == (const P &b) const { 29 return x == b.x && y == b.y; 30 } 31 inline bool operator < (const P &b) const { 32 return x == b.x ? y < b.y : x < b.x; 33 } 34 inline P operator + (const P &b) const { 35 return P(x + b.x, y + b.y); 36 } 37 inline P operator - (const P &b) const { 38 return P(x - b.x, y - b.y); 39 } 40 inline ll operator * (const P &b) const { 41 return x * b.y - y * b.x; 42 } 43 } a[N]; 44 45 struct Line { 46 int a, b; 47 ll len; 48 P mid; 49 L() {} 50 L(int _a, int _b, ll _l, P _m) : a(_a), b(_b), len(_l), mid(_m) {} 51 52 inline bool operator == (const L &b) const { 53 return len == b.len && mid == b.mid; 54 } 55 inline bool operator < (const L &b) const { 56 return len == b.len ? mid < b.mid : len < b.len; 57 } 58 } l[M]; 59 60 inline ll read() { 61 ll x = 0, sgn = 1; 62 char ch = getchar(); 63 while (ch < ‘0‘ || ‘9‘ < ch) { 64 if (ch == ‘-‘) sgn = -1; 65 ch = getchar(); 66 } 67 while (‘0‘ <= ch && ch <= ‘9‘) { 68 x = x * 10 + ch - ‘0‘; 69 ch = getchar(); 70 } 71 return sgn * x; 72 } 73 74 inline ll sqr(ll x) { 75 return (ll) x * x; 76 } 77 78 inline ll dist(P a, P b) { 79 return (ll) sqr(a.x - b.x) + sqr(a.y - b.y); 80 } 81 82 inline ll abs_ll(ll x) { 83 return x < 0 ? -x : x; 84 } 85 86 int main() { 87 int i, j; 88 n = read(); 89 for (i = 1; i <= n; ++i) 90 a[i].x = read(), a[i].y = read(); 91 for (i = 1; i < n; ++i) 92 for (j = i + 1; j <= n; ++j) 93 l[++tot] = L(i, j, dist(a[i], a[j]), a[i] + a[j]); 94 sort(l + 1, l + tot + 1); 95 for (i = 1; i <= tot; ++i) 96 for (j = i - 1; j && l[i] == l[j]; --j) 97 ans = max(ans, abs_ll((a[l[i].a] - a[l[j].a]) * (a[l[i].a] - a[l[j].b]))); 98 printf("%lld\n", ans); 99 return 0;100 }
BZOJ2338 [HNOI2011]数矩形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。