이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
bool was = 0;
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;
was = 1;
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];
}
}
assert(was);
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 && (x[vl] < 0 || y[vl] < 0)) {
if (area(x[i], y[i], x[j], y[j], x[vl], y[vl]) != 0)
events.PB({i + 1, j + 1, vl + 1});
else if (area(x[z], y[z], x[j], y[j], x[vl], y[vl]) != 0)
events.PB({z + 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |