洛谷 P2202 [USACO13JAN]方块重叠Square Overlap
Description
在一个直角坐标系中，有N个边长为K的正方形。
给出每一个正方形的中心，请判断所有的正方形是否有重叠。
输入数据保证每一个正方形的中心不重合
Input
* 第1行 ：两个正整数： N , K
其中：2 <= N <= 50 000 ，1 <= K <= 1 000 000 ，K保证是偶数
*第2 .. i+1行：每行有两个整数xi，yi，描述了第i个正方形的中心。
其中：xi，yi均在[-1 000 000，1 000 000]内
Output
只输出一行：
如果没有正方形重叠，输出“0”；如果有且只有一对正方形重叠，输出它们重叠的面积；如果有两对及以上的正方形重合，输出"-1";
注意：在输出答案后一定要输换行符！
Sample Input
4 60 08 4-2 10 7
Sample Output
20
题解：
- 模拟。
- 正解貌似是线性扫描，其实是优化的暴力。但是我这种本人玄学优化的代码就卡过去了。
- 正常写就是直接判断是否重叠然后算重叠面积，O(n ^ 2)
- 我无非就是以x为关键字排了个序，其它做法同上，O(n * ?)，
轻轻松松被卡成O(n ^ 2) - 这题稍微麻烦点的就是算重叠面积。首先重叠面积 = 重叠水平距离 * 重叠竖直距离。
- 水平距离因为是按照x排了序的，所以很容易得出。竖直距离是需要分类讨论一下，经过我手画之后，有以下3种情况：
- 然后依据图片分别就可以容易算出竖直距离了。
#include#include #include #define N 50005using namespace std;struct A {int x, y;} a[N];int n, k, ans, tot;int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}bool cmp(A u, A v) {return u.x < v.x;}int main(){ n = read(), k = read(), k /= 2; for(int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read(); sort(a + 1, a + 1 + n, cmp); for(int i = 1; i < n; i++) { int j = i + 1; while(a[i].x + k > a[j].x - k && j <= n) { int len1 = a[i].x + k - a[j].x + k, len2 = 0, tmp; if(a[i].y == a[j].y) len2 = 2 * k; else if(a[i].y + k >= a[j].y - k && a[j].y - k >= a[i].y - k) len2 = a[i].y + k - a[j].y + k; else if(a[i].y - k <= a[j].y + k && a[j].y + k <= a[i].y + k) len2 = a[j].y + k - a[i].y + k; tmp = len1 * len2; if(tmp) { ans = tmp; if(++tot == 2) {cout << -1 << endl; return 0;} } j++; } } if(!tot) cout << 0 << endl; else cout << ans << endl; return 0;}