Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int inf = 1e9;
- const int N = 150 + 10;
- vector <int> coor;
- int x[N], y[N];
- int dis[N][N];
- bool ar[N][N];
- int n, sz;
- int distance(int x1, int y1, int x2, int y2){
- int dx = abs(x1 - x2);
- int dy = abs(y1 - y2);
- return dx * dx + dy * dy;
- }
- int Find(int x){
- int l = 0, r = sz - 1;
- while(l <= r){
- int mid = (l + r) / 2;
- if(coor[mid] == x) return mid;
- else if(coor[mid] > x) r = mid - 1;
- else l = mid + 1;
- }
- }
- int main(){
- scanf("%d", &n);
- for(int i=1;i<=n;i++)
- scanf("%d%d", &x[i], &y[i]);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- dis[i][j] = distance(x[i], y[i], x[j], y[j]);
- coor.push_back(dis[i][j]);
- }
- }
- sort(coor.begin(), coor.end());
- coor.resize(unique(coor.begin(), coor.end()) - coor.begin());
- sz = coor.size();
- vector <int> qs(sz + 10, 0);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- scanf("%d", &ar[i][j]);
- if(i == j) continue;
- int idx = Find(dis[i][j]);
- if(ar[i][j]){
- qs[idx] ++;
- }
- else{
- qs[0] ++;
- qs[idx] --;
- }
- }
- }
- int mx = 0;
- for(int i=1;i<sz;i++){
- qs[i] += qs[i-1];
- mx = max(mx, qs[i]);
- }
- printf("%d", n * n - (mx + n));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement