Codeforce 1163 C2. Power Transmission (Hard Edition) 解析(思維、幾何)

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

題目
給一堆點，每兩個點會造成一個直線，求有多少個直線對相交。

前言

這題提供了一個表達直線的方法。

想法

這題的難點其實是在於如何表達一條直線，且要認為用$map$不會超時(我也不懂為什麼最多會有$10^6$個不同的值但是不到$1$秒就跑完了)。
表達一個直線，我們從一般的直線表達式$y=ax+b$出發，目前$a,b$很有可能不是整數。我們把整個表達式乘上一個$C$，變成$Cy=Cax+Cb$，我們把$Ca=A,Cb=B$，也就是$A,B,C$是整數。
接著代入兩點，得到$\frac{A}{C}=\frac{y_2-y_1}{x_2-x_1}$。接下來，由於我們希望對於同一條直線，我們得到的$A,B,C$都是完全相同的，因此我們先令$g=gcd(\frac{|\Delta y|}{|\Delta x|})$ where $\Delta y=y_2-y_1,\Delta x=x_2-x_1$，接著$C=\frac{\Delta x}{g},A=\frac{\Delta y}{g}$，之後再計算出$B=\frac{x_1y_2-x_2y_1}{g}$。
最後還需要

if(A<0)A=-A,C=-C,B=-B;if(A==0 and C<0)C=-C,B=-B;  

我們要用兩個$map$分別紀錄${A,C,B}$出現過了沒(當同樣的直線出現過時才能忽略)，和紀錄${A,C}$出現了幾次(紀錄每種斜率的平行線段有多少個)。

接著只要遍歷所有出現過的斜率把答案加上即可。

程式碼:

const int _n=1010;  
int t,n,x,y,g,A,B,C,cnt;  
PII pts[_n];  
struct L{  
  int A,C,B;  
  bool operator<(const L& rhs)const{  
    if(A==rhs.A){  
      if(B==rhs.B)return C<rhs.C;  
      return B<rhs.B;  
    }return A<rhs.A;  
  }  
};  
map<L,int> mp;  
map<PII,int> mp2;  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n;rep(i,1,n+1)cin>>pts[i].fi>>pts[i].se;  
  rep(i,1,n)rep(j,i+1,n+1){  
    x=pts[j].fi-pts[i].fi,y=pts[j].se-pts[i].se,g=__gcd(abs(x),abs(y));  
    A=y/g,C=x/g,B=(pts[i].fi*pts[j].se-pts[j].fi*pts[i].se)/g;  
    if(A<0)A=-A,C=-C,B=-B;if(A==0 and C<0)C=-C,B=-B;  
    if(!mp[{A,C,B}]){  
      mp[{A,C,B}]++,mp2[{A,C}]++,cnt++;  
    }  
  }ll ans=0;  
  for(auto it=mp2.begin();it!=mp2.end();it++){  
    A=it->fi.fi,C=it->fi.se;  
    ans+=1ll*mp2[{A,C}]*(cnt-mp2[{A,C}]);  
  }cout<<ans/2<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission