Rasheda And The Zeriba Gym - 100283A  计算几何

​​http://codeforces.com/gym/100283/problem/A​​

考虑到多边形是不稳定的，是可以变来变去的。

那么总是可以把每个点放到圆上。

所以只需要判断圆心角是不是小于等于360即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1000 + 20;
int a[maxn];
const double eps = 1e-6;
int n;
double pi = acos(-1.0);
bool check(double r) {
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        res += asin(a[i] / 2.0 / r);
    }
    return res <= pi;
}
void work() {
    int sum = 0;
    int mx = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        mx = max(a[i], mx);
        sum += a[i];
    }
    static int f = 0;
    printf("Case %d: ", ++f);
    if (sum - mx <= mx) {
        cout << "can't form a convex polygon" << endl;
        return;
    }
    double be = 0, en = 3e6 + 20;
    while (be + eps < en) {
        double mid = (be + en) / 2;
        if (check(mid)) {
            en = mid;
        } else be = mid;
    }
    printf("%.4f\n", en);
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    freopen("zeriba.in", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--) work();
    return 0;
}

View Code