oj.uz

Submission #250427

# Submission time Handle Problem Language Result Execution time Memory
250427 2020-07-17T20:34:54 Z VEGAnn Paralelogrami (COCI17_paralelogrami) C++14
28 / 140
 1 ms 384 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;

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    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 (nw[it] > -11 && nw[it + 1] > -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 (vl != i && vl != j && vl != z)
                events.PB({i + 1, j + 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 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB selected three points is not collinear
3 Halted 0 ms 0 KB -

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 1 ms 384 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB selected three points is not collinear
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB point not in first quadrant exists
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB point not in first quadrant exists
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB point not in first quadrant exists
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB point not in first quadrant exists
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB point not in first quadrant exists
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB point not in first quadrant exists
3 Halted 0 ms 0 KB -