oj.uz

Submission #129783

# Submission time Handle Problem Language Result Execution time Memory
129783 2019-07-13T08:22:31 Z forestryks Paralelogrami (COCI17_paralelogrami) C++14
140 / 140
 13 ms 1940 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define left left123
#define right right123

struct pt {
    ll x, y;
    int id = 0;
};

ll dot(const pt &a, const pt &b) {
    return a.x * b.x + a.y * b.y;
}

ll cross(const pt &a, const pt &b) {
    return a.x * b.y - a.y * b.x;
}

pt operator-(const pt &a, const pt &b) {
    return {a.x - b.x, a.y - b.y};
}

pt operator+(const pt &a, const pt &b) {
    return {a.x + b.x, a.y + b.y};
}

pt get(const pt &a, const pt &b) {
    return b - a;
}

ll sig(ll x) {
    if (x < 0) return -1;
    if (x > 0) return 1;
    return 0;
}

bool bet(const pt &a, const pt &b, const pt &c) {
    if (cross(a, b) >= 0 && cross(b, c) >= 0) return true;
    if (cross(a, b) <= 0 && cross(b, c) <= 0) return true;
    return false;
}

pt rot(const pt &a, const pt &b, const pt &c) {
    pt r = a + b - c;
    r.id = c.id;
    return r;
}

bool operator<(const pt &a, const pt &b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool operator==(const pt &a, const pt &b) {
    return (a.x == b.x && a.y == b.y);
}

const int MAXN = 405;
int n;
pt a[MAXN];
vector<tuple<int, int, int>> ans;

vector<pt> bfs() {
    vector<pt> bg = {a[0], a[1], a[2]};
    queue<vector<pt>> q;
    map<vector<pt>, pair<vector<pt>, int>> p;
    q.push(bg);
    p[bg] = {{}, -1};

    while (!q.empty()) {
        // cout << "ok" << endl;
        auto t = q.front();
        q.pop();

        // cout << t[0].x << ' ' << t[0].y << ' ' << t[1].x << ' ' << t[1].y << ' ' << t[2].x << ' ' << t[2].y << endl;

        if (max(t[0].x, max(t[1].x, t[2].x)) < -10) continue;
        if (max(t[0].y, max(t[1].y, t[2].y)) < -10) continue;

        if (min(t[0].x, min(t[1].x, t[2].x)) >= 5 && min(t[0].y, min(t[1].y, t[2].y)) >= 5) {
            auto v = t;

            while (true) {
                int i = p[t].s;
                // cout << i << endl;
                if (i == -1) break;
                ans.push_back({(i + 1) % 3, (i + 2) % 3, i});
                t = p[t].f;
            }
            reverse(all(ans));

            return v;
        }

        rep(i, 3) {
            auto nt = t;
            nt[i] = rot(nt[(i + 1) % 3], nt[(i + 2) % 3], nt[i]);
            if (p.find(nt) == p.end()) {
                p[nt] = {t, i};
                q.push(nt);
            }
        }
    }

    assert(false);
}

int main() {
    FAST_IO;
    bool ok = false, bad = false;
    cin >> n;
    rep(i, n) {
        cin >> a[i].x >> a[i].y;
        a[i].id = i;
        if (a[i].x < 0 || a[i].y < 0) {
            bad = true;
        }
    }

    if (!bad) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 2; i < n; ++i) {
        if (cross(get(a[0], a[i]), get(a[1], a[i])) != 0) {
            swap(a[2], a[i]);
            ok = true;
            break;
        }
    }

    if (!ok) {
        cout << -1 << endl;
        return 0;
    }

    auto t = bfs();

    for (int i = 3; i < n; ++i) {
        if (a[i].x >= 0 && a[i].y >= 0) {
            continue;
        }

        if (cross(get(a[i], t[0]), get(a[i], t[1])) == 0) {
            ans.push_back({0, 2, i});
        } else {
            ans.push_back({0, 1, i});
        }
    }

    assert(ans.size() <= 2500);

    cout << ans.size() << '\n';
    for (auto it : ans) {
        int i, j, k;
        tie(i, j, k) = it;
        cout << a[i].id + 1 << ' ' << a[j].id + 1 << ' ' << a[k].id + 1 << '\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 516 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1940 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1912 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1144 KB Output is correct
2 Correct 9 ms 1656 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 1784 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 9 ms 1656 KB Output is correct
3 Correct 3 ms 504 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 1656 KB Output is correct
3 Correct 2 ms 376 KB Output is correct