yukicoder 1041 直線大学 - chacoderのブログ

問題

N個の　座標　Xi,Yiにある点のうち同一直線上にある点の個数の最大値を求める問題です。
制約（2<=N<=100 0<= Xi,Yi<=100)

考察

幾何問題は何となく苦手感がありますがさほど難しいことは要求されず必要な数学知識は限られています。

３点A,B,Cが同一直線上にあるということは線分ABと線分BCの傾きが同じということでありX座標の差とY座標の差の比が同じということです。
AとBのすべての場合を全探索し，更にCを全探索します。
N<=100なので10^6程度で計算量も大丈夫です。

同一直線上判定は割り算で比を出すと誤差を生じるで，式変形して積の形で比較するようにします。

カウントされた３点目の数の最大値にABの２点を加えた値が答えになります。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin>>n;
  int x[n];
  int y[n];
  for(int i=0;i<n;i++){
    cin>>x[i]>>y[i];
  }
  int cnt=0;
  int maxcnt=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      cnt=0;
      for(int k=j+1;k<n;k++){
        if((x[k]-x[j])*(y[j]-y[i])==(x[j]-x[i])*(y[k]-y[j]) ){
          cnt++;
        }
      }
      maxcnt=max(maxcnt,cnt);
    }
  }
  cout<<maxcnt+2<<endl;
  return 0;
}