Codeforce 660 D. Number of Parallelograms 解析(幾何)

今天我們來看看CF660D
題目連結

題目
給你一些點，求有多少個平行四邊形。

前言

a

想法

注意到，只要有兩個等長的平行邊，那我們就找到了一個平行四邊形了。
所以只要用一個$map$紀錄每個線段出現的次數，且每次加入一個線段(我們枚舉線段)時，先把答案加上目前有多少等長平行線段，最後答案除以二就行了。

程式碼:

const int _n=2010;  
int t,n,x,y;  
vector<PII> ps;  
map<PII,int> cnt;  
ll ans;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n;rep(i,0,n){cin>>x>>y;ps.pb({x,y});}  
  rep(i,0,n-1)rep(j,i+1,n){  
    PII v={ps[j].fi-ps[i].fi,ps[j].se-ps[i].se};  
    if(v.fi<0)v.fi=-v.fi,v.se=-v.se;  
    if(v.fi==0 and v.se<0)v.se=-v.se;  
    ans+=cnt[v]; cnt[v]++;  
  }cout<<ans/2<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission