HackerRank Week of Code 23-Enclosure(등주정리+여현정리)

Vigo the Carpathian is an evil feudal lord. He wants to seize land from his serfs by enclosing it with a polygonal fence where each respective side has a strictly specified length. Can you help him maximize the fenced area?
Given a sequence of n lengths (i.e., L1,L2,⋯,Ln ) where each is the length of the kth side, find a sequence of points (where pk=(xk,yk) ) such that dist (pk,pk+1)=Lk and dist (p1,pn)=Ln where dist (a,b)is the Euclidean distance between points a and b. Note that the first point, p1 , must be (0,0)and the second point, p2 , must be (0,L1) . These points must correspond to the ordered clockwise vertices of the simple polygon having the maximum possible area for the given side lengths. Then print the points according to the instructions in the Output Format section below.
Input Format
The first line contains a single integer,n , denoting the number of sides in the polygon. The second line contains n space-separated positive integers describing each respective Lk . It is guaranteed that you can form an -edge polygon with the given sequence of lengths.
Constraints

3≤n≤104

1≤LK≤104

Output Format
For each of the n points (i.e., vertices in the polygon), print three lines in the following format:

The first line must contain a single floating-point number denoting the point's x-coordinate.
The second line must contain a single floating-point number denoting the point's y-coordinate.
The third line must be empty and serves as a visual spacer between the last point's -coordinate and the next point's x-coordinate.

You must print a total of 3*n lines of output. Your output is considered to be correct if the absolute difference from the correct answer for each coordinate is not greater than 10−1 . It is guaranteed that the exact correct answer is unique.
Sample Input 0
4 1 2 1 2
Sample Output 0
0.000000 0.000000
0.000000 1.000000
2.000000 1.000000
2.000000 0.000000
Explanation 0
The enclosure is a quadrilateral (specifically, a parallellogram). The area enclosed by the fence is maximal when it’s a rectangle.
Sample Input 1
3 1 1 1
Sample Output 1
0.000000 0.000000
0.000000 1.000000
0.866025 0.500000
Explanation 1
The only possible polygon is an equilateral triangle.
시계 바늘의 순서에 따라 n변형의 길이를 주고 n변형의 n정점의 좌표를 출력하여 다각형의 면적을 가장 크게 한다.
둘레가 이미 알았을 때 다각형의 면적은 원의 면적에 가까울수록 커지기 때문에 마지막 다각형은 반드시 외접원이 있고 다각형의 변장은 원의 현길이이다.그래서 우리는 이 조건에 따라 대응하는 원심각을 구할 수 있다.그래서 우리는 원심각의 크기에 따라 선택한 직경이 적당한지 아닌지를 판단할 수 있다.원의 직경을 이분한 다음에 벡터를 회전시켜 좌표를 구한다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int maxn = 1e4+100;
double a[maxn];
struct node{
    double x,y;
    node(){}
    node(double _x,double _y):x(_x),y(_y){}
    node operator + (const node &b)const  {
        return node(x+b.x,y+b.y);
    }
    node operator * (const double &b) const{ //    
        return node(x*cos(b)-y*sin(b),x*sin(b)+y*cos(b));
    }
}ans[maxn];
int main(){
    int n;
    scanf("%d",&n);
    double r = 0;
    for(int i = 0;i<n;i++) {
        scanf("%lf",&a[i]);
        r+=a[i];
    }
    int mx = 0;
    for(int i = 1;i<n;i++) if(a[i]>a[mx]) mx = i;
    double l = a[mx]/2;
    double phi = 0;
    for(int i = 0;i<n;i++) {
            if(i != mx)phi += acos(1-a[i]*a[i]/(2*l*l));
    }
    bool flag = phi<pi;
    r *=2;
    while(r-l>eps) {//    
        double mid = (l+r)/2;
        double phi = 0;
        for(int i = 0;i<n;i++) if(i!=mx) phi += acos(1-a[i]*a[i]/(2*mid*mid));
        double phii = acos(1-a[mx]*a[mx]/(2*mid*mid));
        if(flag) {
            if(phi<phii) l = mid;
            else r = mid;
        }
        else {
            if(phi+phii > 2*pi) l = mid;
            else r = mid;
        }
    }
    r = l;
    ans[0].x = 0; ans[0].y = 0;
    ans[1].x = 0,ans[1].y= a[0];
    node ve,circ;
    if(flag && mx == 0) {//           
        ve.x = sqrt(r*r-a[0]*a[0]/4);
        ve.y = a[0]/2;
        circ.x = -ve.x; circ.y = a[0]/2;
    }
    else {
        ve.x = -sqrt(r*r-a[0]*a[0]/4);
        ve.y = a[0]/2;
        circ.x = -ve.x; circ.y = ve.y;
    }
    for(int i = 1;i<n;i++) {
        double c = acos(1-a[i]*a[i]/(2*r*r));
        if(flag && i ==mx) c = 2*pi-c;
        c = -c;
        ve = ve*c;
        ans[i+1] = circ+ve;
    }
    for(int i = 0;i<n;i++) printf("%.6f
%.6f

",ans[i].x,ans[i].y);
    return 0;
}