Submission #57742

#	Time	Username	Problem	Language	Result	Execution time	Memory
57742		polyfish	Pick (COI18_pick)	C++14	50 / 100	1074 ms	924 KiB

pick

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define y1 _y1_
#define y2 _y2_

typedef pair<int, int> point;

class polygon {
public:
    vector<point> bound;

    void ins(point G) {
        bound.push_back(G);
    }

    int area() {
        int res = 0;
        for (int i=0; i<bound.size(); ++i) {
            int j = (i + 1 + bound.size()) % bound.size();
            res += (bound[i].x * bound[j].y - bound[i].y * bound[j].x);
        }
        return abs(res);
    }
} res;
int a, b, c, d;

void solve(int x1, int x2, int y1, int y2, int z1, int z2, int z3, int z4) {
    polygon p;
    point cur(0, 0);
    p.ins(cur);
    for (int i=1; i<=x2; ++i) {
        --cur.x;
        p.ins(cur);
    }
    for (int i=1; i<=z1; ++i) {
        --cur.x;
        ++cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=z4; ++i) {
        --cur.x;
        --cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=y2; ++i) {
        --cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=z3; ++i) {
        ++cur.x;
        --cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=x1; ++i) {
        ++cur.x;
        p.ins(cur);
    }
    for (int i=1; i<=z2; ++i) {
        ++cur.x;
        ++cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=y1; ++i) {
        ++cur.y;
        p.ins(cur);
    }
    if (cur != point(0, 0))
        return;
    p.bound.pop_back();
    if (res.bound.size()==0 || p.area()<res.area()) {
        res = p;
    }
}

int main() {
    //freopen("pick.inp", "r", stdin);
    //freopen("pick.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> a >> b >> c >> d;
    for (int x1=0; x1<=a; ++x1) {
        for (int y1=0; y1<=b; ++y1) {
            for (int z1=0; z1<=d; ++z1) {
                for (int z2=0; z2<=c; ++z2) {
                    int x2 = a - x1, y2 = b - y1, z3 = d - z1, z4 = c - z2;
                    solve(x1, x2, y1, y2, z1, z2, z3, z4);
                }
            }
        }
    }
    //cerr << res.area() << '\n';
    for (int i=0; i<(int)res.bound.size(); ++i)
        cout << res.bound[i].x << ' ' << res.bound[i].y << '\n';
}

Compilation message (stderr)

pick.cpp: In member function 'int polygon::area()':
pick.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<bound.size(); ++i) {
                       ~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 20