P8042 [COCI 2016/2017 #7] PARALELOGRAMI 详解
思路
先说明一下，这里的第一象限不是数学意义上的第一象限，也就是点在坐标轴上也算是在第一象限，下文的第一象限全部是这个定义。
若所有点在第一象限，不需要操作。
讨论无解的情况，很明显若不能移动则无解，所以我们只需要判断能不能找出不共线的两个点就可以了。
那其他有没有无解的情况呢？答案是没有，因为这个平行四边形可以覆盖到整个坐标系，可能有点抽象，放一个官解的图。
就是说这三个点就可以随便移动到每个象限，而如果移动完了以后就可以直接对于剩下的点，在三个点中选出不共线的两点进行移动。
难点在于如何将任意三个点移动到第一象限，由于坐标范围很小，不难发现这个过程可以通过搜索完成，初始状态即为开始三个点的坐标，终止状态的话就是三个点的横纵坐标全部大于等于某个值，这个值最好不要太大，可能超时，也不要太小，因为太小可能构成的平行四边形的点仍然不在第一象限，所以我选择了
Code
//# 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;
}我想要天天說，天天說，天天對你說，我有多愛你…………