hdu 4033 Regular Polygon 计算几何 二分+余弦定理

题目链接

给一个n个顶点的正多边形， 给出多边形内部一个点到n个顶点的距离， 让你求出这个多边形的边长。

二分边长， 然后用余弦定理求出给出的相邻的两个边之间的夹角， 看所有的加起来是不是2Pi。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

double a[];

int main()

{

    int t, n;

    cin>>t;

    for(int casee = ; casee<=t; casee++) {

        printf("Case %d: ", casee);

        cin>>n;

        for(int i = ; i<n; i++) {

            scanf("%lf", &a[i]);

        }

        double l = -inf, r = inf;

        for(int i = ; i<n; i++) {

            l = max(l, fabs(a[i]-a[(i+)%n]));

            r = min(r, a[i]+a[(i+)%n]);

        }

        int flag = ;

        while(fabs(r-l)>eps) {

            double mid = (l+r)/, ans = ;

            for(int i = ; i<n; i++) {

                int tmp = (i+)%n;

                ans += acos((a[i]*a[i]+a[tmp]*a[tmp]-mid*mid)/(*a[i]*a[tmp]));

            }

            if(fabs(ans-*PI)<eps) {

                flag = ;

                break;

            }

            if(ans>*PI)

                r = mid;

            else

                l = mid;

        }

        if(flag) {

            printf("%.3f\n", l);

        } else {

            puts("impossible");

        }

    }

    return ;

}