Advertisement
YEZAELP

o59_may03_signal

Nov 17th, 2021
564
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int N = 150 + 10;
  6. vector <int> coor;
  7. int x[N], y[N];
  8. int dis[N][N];
  9. bool ar[N][N];
  10. int n, sz;
  11.  
  12. int distance(int x1, int y1, int x2, int y2){
  13.     int dx = abs(x1 - x2);
  14.     int dy = abs(y1 - y2);
  15.     return dx * dx + dy * dy;
  16. }
  17.  
  18. int Find(int x){
  19.     int l = 0, r = sz - 1;
  20.     while(l <= r){
  21.         int mid = (l + r) / 2;
  22.         if(coor[mid] == x) return mid;
  23.         else if(coor[mid] > x) r = mid - 1;
  24.         else l = mid + 1;
  25.     }
  26. }
  27.  
  28. int main(){
  29.  
  30.     scanf("%d", &n);
  31.  
  32.     for(int i=1;i<=n;i++)
  33.         scanf("%d%d", &x[i], &y[i]);
  34.  
  35.     for(int i=1;i<=n;i++){
  36.         for(int j=1;j<=n;j++){
  37.             dis[i][j] = distance(x[i], y[i], x[j], y[j]);
  38.             coor.push_back(dis[i][j]);
  39.         }
  40.     }
  41.     sort(coor.begin(), coor.end());
  42.     coor.resize(unique(coor.begin(), coor.end()) - coor.begin());
  43.     sz = coor.size();
  44.     vector <int> qs(sz + 10, 0);
  45.  
  46.     for(int i=1;i<=n;i++){
  47.         for(int j=1;j<=n;j++){
  48.             scanf("%d", &ar[i][j]);
  49.             if(i == j) continue;
  50.             int idx = Find(dis[i][j]);
  51.             if(ar[i][j]){
  52.                 qs[idx] ++;
  53.             }
  54.             else{
  55.                 qs[0] ++;
  56.                 qs[idx] --;
  57.             }
  58.         }
  59.     }
  60.  
  61.     int mx = 0;
  62.     for(int i=1;i<sz;i++){
  63.         qs[i] += qs[i-1];
  64.         mx = max(mx, qs[i]);
  65.     }
  66.  
  67.     printf("%d", n * n - (mx + n));
  68.  
  69.     return 0;
  70. }
Advertisement
RAW Paste Data Copied
Advertisement