题解 CF1091B 【New Year and the Treasure Geolocation】
小黑AWM
2018-12-31 18:39:27
此题不难想到$O(n^2)$的做法，即将所有的$(x,y)$和$(a,b)$一一配对，用map统计每种$(x+a,y+b)$出现的次数，出现n次的即为答案。
但是我用这个做法莫名第八点RE
```cpp
#include <cstdio>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
int n, x[maxn], y[maxn], a, b;
pair<int, int> storage[maxn];
int top;
map<pair<int, int>, int> func;
int main(){
cin >> n;
for(int i = 1 ; i <= n; i++)
cin >> x[i] >> y[i];
for(int i = 1 ; i <= n; i++){
cin >> a >> b;
for(int j = 1; j <= n; j++){
func[make_pair(x[j]+a, y[j]+b)]++,
storage[++top] = make_pair(x[j]+a, y[j]+b);
if(func[make_pair(x[j]+a, y[j]+b)] == n){
cout << x[j]+a << " " << y[j]+b << endl;
return 0;
}
}
}
return 0;
}
```
那就得想其他做法，我们不难发现，
_当所有的(x+a,y+b)一样的时候，$n(x+a) = \sum{xi}+\sum{ai}$_ 对于$(y+b)$同理，那么问题迎刃而解。
需要注意的是，当我们求和的时候要开long long因为最大的时候是(1e6+2e6)*1e3 = 3e9刚刚好爆了int，而Pretest里是没有这样的数据的（~~所以我被hack了~~
```cpp
#include <cstdio>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
long long n, x, y, sumx, sumy;
int main(){
cin >> n;
for(int i = 1 ; i <= 2*n; i++)
cin >> x >> y,
sumx += x,
sumy += y;
cout << sumx/n << " " << sumy/n << endl;
return 0;
}
```