首页 > 代码库 > Rasheda And The Zeriba Gym - 100283A ? 计算几何
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; }
Rasheda And The Zeriba Gym - 100283A ? 计算几何
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。