oj.uz

Submission #250440

# Submission time Handle Problem Language Result Execution time Memory
250440 2020-07-17T21:35:24 Z VEGAnn Paralelogrami (COCI17_paralelogrami) C++14
140 / 140
 4 ms 768 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define PB push_back
#define i3 array<int,3>
#define i6 array<int,6>
#define sz(x) ((int)x.size())
using namespace std;
const int N = 410;
const int oo = 2e9;
map<i6, i6> mem;
queue<i6> qu;
vector<i3> events;
int x[N], y[N], n;

int area(int x1, int y1, int x2, int y2, int x3, int y3){
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    bool very_good = 1;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        very_good &= bool(x[i] >= 0 && y[i] >= 0);
    }

    if (very_good){
        cout << 0;
        return 0;
    }

    for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
    for (int z = j + 1; z < n; z++){
        if (area(x[i], y[i], x[j], y[j], x[z], y[z]) == 0) continue;

        i6 sta = {x[i], y[i], x[j], y[j], x[z], y[z]};

        mem[sta] = {-oo, -oo, -oo, -oo, -oo, -oo};

        qu.push(sta);

        while (sz(qu) > 0){
            i6 cur = qu.front(); qu.pop();

            bool bad = 0;

            for (int it = 0; it < 6; it++)
                if (cur[it] < 5) {
                    bad = 1;
                    break;
                }

            if (!bad){
                sta = cur;
                break;
            }

            i6 nw = cur;

            int sx = cur[0] + cur[2] + cur[4];
            int sy = cur[1] + cur[3] + cur[5];

            for (int it = 0; it < 6; it += 2){
                nw[it] = sx - cur[it] - cur[it];
                nw[it + 1] = sy - cur[it + 1] - cur[it + 1];

                if (max(nw[0], max(nw[2], nw[4])) > -11 &&
                    max(nw[1], max(nw[3], nw[5])) > -11 &&
                    mem.find(nw) == mem.end()){

                    mem[nw] = cur;

                    qu.push(nw);
                }

                nw[it] = cur[it];
                nw[it + 1] = cur[it + 1];
            }
        }

        events.clear();

        i6 cur = sta;

        while (1){
            i6 pre = mem[cur];

            if (pre[0] == -oo) break;

            i6 nw = cur;

            int sx = cur[0] + cur[2] + cur[4];
            int sy = cur[1] + cur[3] + cur[5];

            for (int it = 0; it < 6; it += 2){
                nw[it] = sx - cur[it] - cur[it];
                nw[it + 1] = sy - cur[it + 1] - cur[it + 1];

                if (nw == pre){
                    if (it == 0)
                        events.PB({j + 1, z + 1, i + 1});
                    else if (it == 2)
                        events.PB({i + 1, z + 1, j + 1});
                    else events.PB({i + 1, j + 1, z + 1});

                    break;
                }

                nw[it] = cur[it];
                nw[it + 1] = cur[it + 1];
            }

            cur = pre;
        }

        reverse(all(events));

        for (int vl = 0; vl < n; vl++)  {
            if (x[vl] >= 0 && y[vl] >= 0) continue;

            if (vl != i && vl != j && vl != z) {
                if (area(sta[0], sta[1], sta[2], sta[3], x[vl], y[vl]) != 0)
                    events.PB({i + 1, j + 1, vl + 1});
                else events.PB({i + 1, z + 1, vl + 1});
            }
        }

        cout << sz(events) << '\n';

        for (i3 cr : events)
            cout << cr[0] << " " << cr[1] << " " << cr[2] << '\n';

        return 0;
    }

    cout << -1;

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 768 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 756 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 0 ms 384 KB Output is correct