1940:Polygon Programming with Ease

keyword

平面幾何　二分探索　C++

概要

1939:Diplomatic Licenseの入出力を逆にした問題。
普通にやると連立1次方程式を解くことになる。係数行列が複雑でないので多分普通に解けるけど、面倒なので2分探索で解く。nが奇数なので、1ヶ所固定して1周した後戻ってくるとき、真の解より大きい(小さい)値から始めると最初に固定した点より小さい(大きい)値になってしまう。この単調性から2分探索が効く。

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        vector<double> xs(n),ys(n);
        double x, y;
        for(int i=0; i<n; i++){
            scanf("%lf%lf",&xs[i],&ys[i]);
        }
        double low = -1e13, high = 1e13, mid, tmp;
        for(int loop=0; loop<100; loop++){
            mid = (high+low)*0.5;
            tmp = mid;
            for(int i=0; i<n; i++){
                tmp = 2*xs[i]-tmp;
            }
            if(tmp < mid){
                high = mid;
            }
            else{
                low = mid;
            }
        }
        x = mid;
        low = -1e13, high = 1e13;
        for(int loop=0; loop<100; loop++){
            mid = (high+low)*0.5;
            tmp = mid;
            for(int i=0; i<n; i++){
                tmp = 2*ys[i]-tmp;
            }
            if(tmp < mid){
                high = mid;
            }
            else{
                low = mid;
            }
        }
        y = mid;

        printf("%d ",n);
        for(int i=0; i<n; i++){
            printf("%.6f %.6f%c",x+EPS,y+EPS,(i==n-1)?'\n':' ');
            x = 2*xs[i]-x;
            y = 2*ys[i]-y;
        }
    }

    return 0;
}