#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 = 1000;
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], a[0]), get(a[i], a[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';
}
}
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
selected three points is not collinear |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
selected three points is not collinear |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2040 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
selected three points is not collinear |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1912 KB |
Output is correct |
2 |
Correct |
2 ms |
396 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
10 ms |
1656 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
8 ms |
1656 KB |
Output is correct |
3 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
9 ms |
1528 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |