SRM272 DIV2 1000 vectorpolygon

問題

　N個の2次元ベクトルが与えられる。このベクトルからいくつかを選び適切な順に並べ直し、凸多角形を作る。作ることのできる凸多角形のうち面積が最大のものの面積を求めよ。凸多角形が作れない場合は0を出力せよ。
　1≦N≦8

方針

　x軸となす角度が小さい順にベクトルを並べ替える。適当に選んだベクトル集合の和がゼロベクトルなら閉じた領域を作れる。 　あとは凸判定だけど、x軸となす角が小さい順に辺が並んでいるので凸になっている。（逆に凸多角形ならば、辺を反時計まわりにみれば辺とx軸がなす角はかならず増えていく。） 　面積は外積を使って計算できる。

ソースコード

view plainprint?

1. using namespace std;  
2.   
3. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
4. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
5.   
6. class VectorPolygon {  
7.     template <class T> T crossProduct(T x1, T y1, T x2, T y2) {  
8.         return x1*y2 - x2*y1;  
9.     }  
10.   
11.     double getArea(vector<int> &x, vector<int> &y) {  
12.         int N = x.size();  
13.   
14.         long long ret = 0;  
15.         REP(i, N) {  
16.             int j = (i+1)%N;  
17.             ret += crossProduct<long long>(x[i], y[i], x[j], y[j]);  
18.         }  
19.   
20.         return 0.5*ret;  
21.     }  
22.   
23.     double getAngle(int x, int y) {  
24.         double ret = atan2(y, x);  
25.         if (ret >= 0)  
26.             return ret;  
27.         else  
28.             return 2*M_PI+ret;  
29.     }  
30.   
31.   
32. public:  
33.     double maxArea(vector<int> dx, vector<int> dy) {  
34.         int N = dx.size();  
35.         REP(i, N) FOR(j, i+1, N) {  
36.             if (getAngle(dx[i], dy[i]) > getAngle(dx[j], dy[j])) {  
37.                 swap(dx[i], dx[j]);  
38.                 swap(dy[i], dy[j]);  
39.             }  
40.         }  
41.   
42.         REP(i, N)  
43.             cout << dx[i] << " " << dy[i] << " " << getAngle(dx[i], dy[i]) << endl;  
44.   
45.         double ret = 0.0;  
46.         vector<int> vx;  
47.         vector<int> vy;  
48.   
49.         REP(mask, 1<<N) {  
50.             vx.clear();  
51.             vy.clear();  
52.             int x = 0;  
53.             int y = 0;  
54.             int z = 0;  
55.   
56.             vx.push_back(0);  
57.             vy.push_back(0);  
58.             REP(i, N) if (mask & 1<<i) {  
59.                 x += dx[i];  
60.                 y += dy[i];  
61.                 if (!x && !y)  
62.                     ++z;  
63.                 else {  
64.                     vx.push_back(x);  
65.                     vy.push_back(y);  
66.                 }  
67.             }  
68.   
69.             if (x || y || (int)vx.size() < 3) continue;  
70.             if (z != 1) continue;  
71.   
72.             ret = max(ret, getArea(vx, vy));  
73.         }  
74.   
75.         return ret;  
76.     }  
77. };  

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

class VectorPolygon {
    template <class T> T crossProduct(T x1, T y1, T x2, T y2) {
        return x1*y2 - x2*y1;
    }

    double getArea(vector<int> &x, vector<int> &y) {
        int N = x.size();

        long long ret = 0;
        REP(i, N) {
            int j = (i+1)%N;
            ret += crossProduct<long long>(x[i], y[i], x[j], y[j]);
        }

        return 0.5*ret;
    }

    double getAngle(int x, int y) {
        double ret = atan2(y, x);
        if (ret >= 0)
            return ret;
        else
            return 2*M_PI+ret;
    }


public:
    double maxArea(vector<int> dx, vector<int> dy) {
        int N = dx.size();
        REP(i, N) FOR(j, i+1, N) {
            if (getAngle(dx[i], dy[i]) > getAngle(dx[j], dy[j])) {
                swap(dx[i], dx[j]);
                swap(dy[i], dy[j]);
            }
        }

        REP(i, N)
            cout << dx[i] << " " << dy[i] << " " << getAngle(dx[i], dy[i]) << endl;

        double ret = 0.0;
        vector<int> vx;
        vector<int> vy;

        REP(mask, 1<<N) {
            vx.clear();
            vy.clear();
            int x = 0;
            int y = 0;
            int z = 0;

            vx.push_back(0);
            vy.push_back(0);
            REP(i, N) if (mask & 1<<i) {
                x += dx[i];
                y += dy[i];
                if (!x && !y)
                    ++z;
                else {
                    vx.push_back(x);
                    vy.push_back(y);
                }
            }

            if (x || y || (int)vx.size() < 3) continue;
            if (z != 1) continue;

            ret = max(ret, getArea(vx, vy));
        }

        return ret;
    }
};