CodeQUEEN 2023 決勝 F - Queen's Crown

AOJ 2373 HullMarathon とよく似た問題。

• 問題へのリンク

問題概要

二次元平面上に 点を以下の条件を満たすように配置する。各点を とし、偏角を とする。

• 点 と、原点との距離は
• 
• 

このとき、多角形 の面積の最大値を求めよ。

制約

• 
• 

考えたこと

ほとんどこの問題と同じ解法で解ける！

drken1215.hatenablog.com

コード

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const double EPS = 1e-10;  // to be set appropriately
const double PI = 3.141592653589793238462643383279502884L;

int main() {
    int N;
    cin >> N;
    vector<double> R(N);
    for (int i = 0; i < N; ++i) cin >> R[i];
    
    // binary search
    double low = 0, high = 1<<29, sum_theta = 0.0;
    vector<double> theta(N-1);
    for (int iter = 0; iter < 100; ++iter) {
        double x = (low + high) / 2;
        sum_theta = 0;
        for (int i = 0; i < N-1; ++i) {
            double c = x / R[i] / R[i+1];
            chmin(c, 1.0 - EPS), chmax(c, -1.0 + EPS);
            theta[i] = acos(c);
            chmax(theta[i], PI/2/N);
            sum_theta += theta[i];
        }
        if (sum_theta < PI*2/3) high = x;
        else low = x;
    }
    
    // calc area
    double res = -R[0] * R[N-1] * sin(PI*2/3) / 2;
    for (int i = 0; i < N-1; ++i) res += R[i] * R[i+1] * sin(theta[i]) / 2;
    cout << fixed << setprecision(10) << res << endl;
}