P8042 [COCI 2016/2017 #7] PARALELOGRAMI 详解

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 4e2 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n;
int x[N], y[N], id[N];

bool ok = true;

struct node{
	int x[4], y[4];
	
	bool operator < (const node &b) const{
		if(x[1] ^ b.x[1]){
			return x[1] < b.x[1];
		}
		
		if(x[2] ^ b.x[2]){
			return x[2] < b.x[2];
		}
		
		if(x[3] ^ b.x[3]){
			return x[3] < b.x[3];
		}
		
		if(y[1] ^ b.y[1]){
			return y[1] < b.y[1];
		}
		
		if(y[2] ^ b.y[2]){
			return y[2] < b.y[2];
		}
		
		return y[3] < b.y[3];
	}
}emp;

map<node, pair<node, int>> from;

struct result{
	int a, b, c;
};

vec<result> f;

node BFS(){
	queue<node> q;
	node start;
	start.x[1] = x[1], start.y[1] = y[1];
	start.x[2] = x[2], start.y[2] = y[2];
	start.x[3] = x[3], start.y[3] = y[3];
	q.push(start);
	from[start] = {emp, -1};
	while(!q.empty()){
		node s = q.fr();
		q.pop();
		
		if(max({s.x[1], s.x[2], s.x[3]}) < -10) continue;
		if(max({s.y[1], s.y[2], s.y[3]}) < -10) continue;
		
		if(min({s.x[1], s.x[2], s.x[3]}) >= 5 && min({s.y[1], s.y[2], s.y[3]}) >= 5){
			node res = s;
			while(1){
				int i = from[s].sec;
				if(i == -1) break;
				f.pb({i % 3 + 1, (i + 1) % 3 + 1, i});//另外两个 
				s = from[s].fir;
			}
			
			return res;
		}
		
		rep(i, 1, 3){
			node now = s;
			now.x[i] = (s.x[1] + s.x[2] + s.x[3]) - 2 * s.x[i];//根据中点坐标公式得出来的，推一下就好了 
		    now.y[i] = (s.y[1] + s.y[2] + s.y[3]) - 2 * s.y[i];
		    if(!from.count(now)){
				from[now] = {s, i};
				q.push(now);
		    }
		}
	}
}

bool check(PII a, PII b, PII c){//叉积判是否在一条直线 
  return (LL)a.fir * (b.sec - c.sec) + (LL)b.fir * (c.sec - a.sec) + (LL)c.fir * (a.sec - b.sec) == 0;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	
	rep(i, 1, n){
		cin >> x[i] >> y[i];
		id[i] = i;
		if(x[i] < 0 || y[i] < 0) ok = false;
	}
	
	if(ok){
		cout << "0";
		return 0;
	}
	
	rep(i, 3, n){
		if(!check({x[1], y[1]}, {x[2], y[2]}, {x[i], y[i]})){//不共线才能搜 
			swap(id[3], id[i]);
			swap(x[3], x[i]);
			swap(y[3], y[i]);
			ok = true;
			break;
		}
	}
	
	if(!ok){
		cout << "-1\n";
		return 0;
	}
	
	node s = BFS();
	reverse(all(f));
	
	rep(i, 4, n){
		if(x[i] >= 0 && y[i] >= 0) continue;
		if(!check({s.x[1], s.y[1]}, {s.x[2], s.y[2]}, {x[i], y[i]})) f.pb({1, 2, i});//检查共线情况 
		else f.pb({1, 3, i});
	}
	
	cout << f.size() << "\n";
	each2(tmp, f){
		cout << id[tmp.a] << " " << id[tmp.b] << " " << id[tmp.c] << "\n";
	}
	
	return 0;
}