Wannafly挑戰賽26

• 2020 年 2 月 18 日
• 筆記

A. 御坂網路

AC WA 三次是因為.1.程式碼確實寫錯 2. 算n-1個點到這個點的距離去了. 3. emm.想到了正確的演算法.但是應該輸出沒有換行.然後想想算距離是double.有精度損失呀.換種方式吧.就過了.

題目大意: 平面坐標中有$$n$$個點.是否可以選擇一個點作為圓心.其他$$n-1$$個點在這個圓上.

題解: 圓的方程： $$ (x – a) + (y – b) = r^2$$ 所以只要$O(n^2)$暴力匹配這個方程就行.

#include <bits/stdc++.h>  using namespace std;    typedef long long LL;  #define MAX_N 1100  int n;    struct Point{      LL x,y;  }p[MAX_N];    LL d[MAX_N][MAX_N];    LL dis(Point a, Point b){      return (a.x - b.x)*(a.x - b.x)*1LL + (a.y - b.y) * (a.y - b.y)*1LL;  }    int main(){     // freopen("in.txt", "r", stdin);      ios::sync_with_stdio(0); cin.tie(0);      cin >> n;      for(int i = 0; i < n; ++i){          cin >> p[i].x >> p[i].y;      }      for(int i = 0; i < n; ++i){          for(int j = 0; j < n; ++j){              if(i == j) continue;              d[i][j] = dis(p[j], p[i]);          }      }      for(int i = 0; i < n; ++i){          LL ans;          ans = (i == 0) ?  d[i][1] : d[i][0];          int j;          for(j = 0; j < n; ++j){              if(j == i) continue;              if(ans != d[i][j]) break;          }          if(j == n) {              cout << i+1;              return 0;          }      }      cout << "-1";      return 0;  }