#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <tuple>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 433;
std::vector<std::tuple<int,int,int>> ans;
int n;
struct Point{
int x,y;
Point operator + (const Point &t)const{return Point{x + t.x,y + t.y};}
Point operator - (const Point &t)const{return Point{x - t.x,y - t.y};}
bool operator == (const Point &t)const{return x == t.x && y == t.y;}
int operator * (const Point &t)const{
return x * t.y - y * t.x;
}
int h()const{
return (x + 10) * 21 + (y + 10);
}
}p[maxn];
Point nxt(const Point a,const Point b,const Point c){
return Point{a.x + b.x - c.x,a.y + b.y - c.y};
}
bool chk(const Point a,const Point b,const Point c){
return !(((b - a) * (c - a) == 0) && ((a - b) * (c - b) == 0) && ((a - c) * (b - c) == 0));
}
void oper(const int a,const int b,const int c){
ans.emplace_back(a,b,c);
assert(ans.size() <= 2500);
p[c] = nxt(p[a],p[b],p[c]);
}
int main(){
// std::freopen("paralelogrami.in","r",stdin);
// std::freopen("paralelogrami.out","w",stdout);
std::scanf("%d",&n);
rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
int perm[] = {-1,-1,-1,-1};
rep(i,1,n)
rep(j,i + 1,n)
rep(k,j + 1,n)
if(chk(p[i],p[j],p[k])){
perm[1] = i;
perm[2] = j;
perm[3] = k;
goto ed;
}
ed:
if(perm[1] == -1){
std::puts("-1");
return 0;
}
let move_vec = [&perm](const int a,const int b,const int c){
oper(perm[b],perm[c],perm[a]);
oper(perm[a],perm[b],perm[c]);
};
let other = [](const int a,const int b){
if(1 != a && 1 != b)return 1;
if(2 != a && 2 != b)return 2;
if(3 != a && 3 != b)return 3;
return -1;
};
Point va,vb;
std::vector<Point> vec;
rep(i,1,3)
rep(j,i + 1,3)
vec.push_back(p[perm[i]] - p[perm[j]]),
vec.push_back(p[perm[j]] - p[perm[i]]);
vec.push_back(Point{0,0});
for(size_t i = 0;i < vec.size();i++)
for(size_t j = 0;j < vec.size();j++)
if((vec[i] + vec[j]).x > 0 && (vec[i] + vec[j]).y > 0){
va = vec[i];
vb = vec[j];
}
while(true){
if(p[perm[1]].x >= 20 && p[perm[1]].y >= 20 && p[perm[2]].x >= 20 && p[perm[2]].y >= 20 && p[perm[3]].x >= 20 && p[perm[3]].y >= 20)break;
rep(i,1,3)
rep(j,1,3)
if(i != j && (p[perm[j]] - p[perm[i]]) == va){
move_vec(i,j,other(i,j));
break;
}
rep(i,1,3)
rep(j,1,3)
if(i != j && (p[perm[j]] - p[perm[i]]) == vb){
move_vec(i,j,other(i,j));
break;
}
}
let a = perm[1],b = perm[2],c = perm[3];
rep(i,1,n)
if(i != a && i != b && i != c){
if(chk(p[a],p[b],p[i]))oper(a,b,i);
else if(chk(p[b],p[c],p[i]))oper(b,c,i);
else if(chk(p[a],p[c],p[i]))oper(a,c,i);
}
rep(i,1,n)
assert(p[i].x >= 0),
assert(p[i].y >= 0);
std::printf("%d\n",(int)ans.size());
for(let &t : ans)
std::printf("%d %d %d\n",std::get<0>(t),std::get<1>(t),std::get<2>(t));
// std::fclose(stdin);
// std::fclose(stdout);
return 0;
}
Compilation message
paralelogrami.cpp: In function 'int main()':
paralelogrami.cpp:45:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | std::scanf("%d",&n);
| ~~~~~~~~~~^~~~~~~~~
paralelogrami.cpp:46:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
paralelogrami.cpp:21:57: warning: 'vb.Point::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | bool operator == (const Point &t)const{return x == t.x && y == t.y;}
| ~~~~~~~~~^~~~~~~~~~~
paralelogrami.cpp:76:11: note: 'vb.Point::y' was declared here
76 | Point va,vb;
| ^~
paralelogrami.cpp:21:57: warning: 'va.Point::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | bool operator == (const Point &t)const{return x == t.x && y == t.y;}
| ~~~~~~~~~^~~~~~~~~~~
paralelogrami.cpp:76:8: note: 'va.Point::x' was declared here
76 | Point va,vb;
| ^~
paralelogrami.cpp:21:57: warning: 'vb.Point::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | bool operator == (const Point &t)const{return x == t.x && y == t.y;}
| ~~~~~~~~~^~~~~~~~~~~
paralelogrami.cpp:76:11: note: 'vb.Point::x' was declared here
76 | Point va,vb;
| ^~
paralelogrami.cpp:21:57: warning: 'va.Point::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | bool operator == (const Point &t)const{return x == t.x && y == t.y;}
| ~~~~~~~~~^~~~~~~~~~~
paralelogrami.cpp:76:8: note: 'va.Point::y' was declared here
76 | Point va,vb;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
304 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1085 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1080 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1073 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1078 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
