ABC181-C 備忘録 p.48

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

C - Collinearity

考察の流れ

一次関数…！！！とても苦手

N <= 100 なので、for文を3重にしても大丈夫そう

N 個の点の中の相異なる 3点が同一直線上にあるということは、点A, 点B を通るグラフと、点A, 点C を通るグラフの傾きが同じということ

全探索する！

参考：

３点が一直線上にあるための条件

#include <stdio.h>
int main(){
   int n, x[100]={0}, y[100]={0};
   scanf("%d",&n);
   for(int i=0; i<n; i++){
       scanf("%d%d", &x[i], &y[i]);
   }
   for(int i=0; i<n; i++){
       for(int j=i+1; j<n; j++){
           for(int k=j+1; k<n; k++){
               if( (y[j]-y[i])*(x[k]-x[j]) == (y[k]-y[j])*(x[j]-x[i]) ){
                   printf("Yes\n");
                   return 0;
               }
           }
       }
   }
   printf("No\n");
   return 0;
}

まとめ

・プログラムで解けるように数式をうまく変形すること
・一次関数から逃げなかったので偉い、ということに

引き続き、のんびり精進します。

#備忘録 #AtCoder #ABC #プログラミング #競プロ #C言語 #一次関数