[典型90] 009 - Three Point Angle（★6）

[Q] https://atcoder.jp/contests/typical90/tasks/typical90_i

1. 頂点を原点に平行移動させる
2. 残りの頂点との傾きを全部出してsortする
3. 傾きが近い2頂点と原点とを選ぶ3角形が、一番角度が大きくなりそう
4. 原点にする頂点をN通り全部で試す

Q. 
   |   1
   |    3
   |                  5
---x-----------------------            
   |
   |           2
   |6     
   |
   |4

1. xを原点とみなす
2. 1~6の傾きを出してsortしておく
3. sortして、隣り合うindexで作られる3角形が、解答候補の3角形になりそう
x13
x35
x52
x26
x64
x41
の6通りについて、3角形の角度を求める。
一番大きい角度を解答として保管。

4. 次は1を原点とし、2~6について探索
4. 次は2を原点とし、3~6について探索
...

実装

ld X[2020], Y[2020];

// 3頂点がわかったら、一番大きい角度を返す
ld solve(ll a, ll b, ll c) {
 // a^2=b^2+c^2-2bccosA
 // cosA=(a^2-b^2-c^2)/2bc
 vector<ld> V(3);
 V[0] = dist(X[a], X[b], Y[a], Y[b]);
 V[1] = dist(X[b], X[c], Y[b], Y[c]);
 V[2] = dist(X[c], X[a], Y[c], Y[a]); // 一番大きい辺に対するcosAが一番大きい
 sort(all(V));
 ld cos = (V[1] * V[1] + V[0] * V[0] - V[2] * V[2]) / (2.0 * V[1] * V[0]);
 ld theta = acos(cos) / PI * 180;
 return theta;
}

int main() {
 cincout();

 ll N;
 cin >> N;
 // 傾きとれるから、1つ差を比較していく？
 rep(i, N) cin >> X[i] >> Y[i];

 ld ans = 0.0;
 rep(i, N) {
   vector<pair<ld, ll>> P;  // d, id
   for(ll j=i+1; j<N; ++j){
     // iをげんてんとしたとき、jとの傾きをいれてく。
     ld x = X[j] - X[i];
     ld y = Y[j] - Y[i];
     ld d = oo;
     if (x != 0) {
       d = y / x;
     }
     P.push_back({d, j});
   }
   sort(all(P));
   ll psz = P.size();
   rep(j, psz) {
     ll k1 = P[j].second;
     ll k2 = P[(j + 1) % psz].second;
     ld rad = solve(i, k1, k2);
     chmax(ans, rad);
   }
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/27955391