AtCoder Beginner Contest 224 C - Triangle?
問題の要約
xy平面上に1からNまでの番号の付いたN個の点がある。
点iは(Xi,Yi)にあり,相異なる2点は異なる位置に存在する。
このN点から3点を選ぶとき,選ばれた3点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めよ。
制約
入力はすべて整数
2<=N<=300
-10^9<=Xi,Yi<=10^9
i≠jならば(Xi,Yi)≠(Xj,Yj)
考え方
1,点の番号を1つずらす
1からN => 0からN-1
2,300個から3個を選ぶ組合せは300C3=300!/(300-3)!/3!=300*299*298/6=4455100なので全探索しても間に合う。
よって3重のfor文でよい。
3,選ばれた3点が三角形を作らない条件は,3点が一直線に並んでいるときである。
よって,ベクトルをa,bとすると,a=kbとなる整数kが存在することになる。
1点目を(Xi,Yi),2点目を(Xj,Yj),3点目を(Xk,Yk)とすると,aは(Xj-Xi,Yj-Yi),bは(Xk-Xi,Yk-Yi)と表すことができる。
この整数kが存在するとは,"Xj-XiとYj-Yiの最大公約数でそれぞれを割った値"と"Xk-XiとYk-Yiの最大公約数でそれぞれを割った値"が1倍と-1倍のどちらかで等しくなることである。
4,最大公約数のプログラムはO(logmin(x,y))なのでlog2(10^9)=29なのでギリギリ間に合うかもしれない。
実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<cstdlib>
using namespace std;
long long gcd(long long x, long long y){
if(y != 0){
return gcd(y, x%y);
}else{
return x;
}
}
int main(){
long long N;
cin >> N;
vector<pair<long long, long long>> XY(N);
for(long long i = 0; i < N; i++){
cin >> XY[i].first >> XY[i].second;
}
long long count = 0;
for(long long i = 0; i < N; i++){
for(long long j = i+1; j < N; j++){
long long ax = XY[j].first-XY[i].first;
long long ay = XY[j].second-XY[i].second;
long long gcd_a = gcd(llabs(ax), llabs(ay));
ax /= gcd_a;
ay /= gcd_a;
for(long long k = j+1; k < N; k++){
long long bx = XY[k].first-XY[i].first;
long long by = XY[k].second-XY[i].second;
long long gcd_b = gcd(llabs(bx), llabs(by));
bx /= gcd_b;
by /= gcd_b;
if(!((ax == bx && ay == by) || ( ax == -bx && ay == -by))){
count++;
}
}
}
}
cout << count << endl;
return 0;
}