本场题目确实逆天，前三题赛时无人切，最高分不过一百左右。仍然是一如既往的菜，又爆零了，什么时候才能走出这个圈啊……
\(T1：Polygon\)
考场上一眼计算几何，直接毙掉不做。考完后发现很简单……
正解方法确实抽象……首先，把输入的整点分为 \((奇，奇)\)，\((奇，偶)\)，\((偶，偶)\)，\((偶，奇)\)，这四种类型的点。考虑到只需输出 \(\lfloor \frac{n}{10}\rfloor\)，个点，相对来说不多。又因为是凸多边形，因此考虑按照点两个坐标的奇偶性配对，使得两点的中点为整点，输出即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6;
int n,T;
vector<pair<int,pair<int,int> > > ty1,ty2,ty3,ty4;
map<pair<int,int>,bool> m;
signed main(){
scanf("%lld",&T);
while(T--){
ty1.clear(),ty2.clear(),ty3.clear(),ty4.clear();
bool flag = 0;
scanf("%lld",&n);
for(int i = 1; i <= n; i++){
int u,v;
scanf("%lld%lld",&u,&v);
if(abs(u) % 2 == 1){
if(abs(v) % 2 == 1)ty1.push_back(make_pair(i,make_pair(u,v)));
else ty2.push_back(make_pair(i,make_pair(u,v)));
}
else{
if(abs(v) % 2 == 1)ty3.push_back(make_pair(i,make_pair(u,v)));
else ty4.push_back(make_pair(i,make_pair(u,v)));
}
}
int cnt = 0;
for(int i = 0; i < ty1.size(); i++){
int x1 = ty1[i].second.first,y1 = ty1[i].second.second;
for(int j = i + 1; j < ty1.size(); j++){
int x2 = ty1[j].second.first,y2 = ty1[j].second.second;
if(abs(ty1[i].first - ty1[j].first) == 1)continue;
int x3 = (x1 + x2) / 2,y3 = (y1 + y2) / 2;
if(m.find(make_pair(x3,y3)) != m.end())continue;
m[make_pair(x3,y3)] = 1;
printf("%lld %lld\n",x3,y3);
++cnt;
if(cnt == n / 10){
flag = 1;
break;
}
}
if(flag)break;
}
if(flag)continue;
for(int i = 0; i < ty2.size(); i++){
int x1 = ty2[i].second.first,y1 = ty2[i].second.second;
for(int j = i + 1; j < ty2.size(); j++){
int x2 = ty2[j].second.first,y2 = ty2[j].second.second;
if(abs(ty2[i].first - ty2[j].first) == 1)continue;
int x3 = (x1 + x2) / 2,y3 = (y1 + y2) / 2;
if(m.find(make_pair(x3,y3)) != m.end())continue;
m[make_pair(x3,y3)] = 1;
printf("%lld %lld\n",x3,y3);
++cnt;
if(cnt == n / 10){
flag = 1;
break;
}
}
if(flag)break;
}
if(flag)continue;
for(int i = 0; i < ty3.size(); i++){
int x1 = ty3[i].second.first,y1 = ty3[i].second.second;
for(int j = i + 1; j < ty3.size(); j++){
int x2 = ty3[j].second.first,y2 = ty3[j].second.second;
if(abs(ty3[i].first - ty3[j].first) == 1)continue;
int x3 = (x1 + x2) / 2,y3 = (y1 + y2) / 2;
if(m.find(make_pair(x3,y3)) != m.end())continue;
m[make_pair(x3,y3)] = 1;
printf("%lld %lld\n",x3,y3);
++cnt;
if(cnt == n / 10){
flag = 1;
break;
}
}
if(flag)break;
}
if(flag)continue;
for(int i = 0; i < ty4.size(); i++){
int x1 = ty4[i].second.first,y1 = ty4[i].second.second;
for(int j = i + 1; j < ty4.size(); j++){
int x2 = ty4[j].second.first,y2 = ty4[j].second.second;
if(abs(ty4[i].first - ty4[j].first) == 1)continue;
int x3 = (x1 + x2) / 2,y3 = (y1 + y2) / 2;
if(m.find(make_pair(x3,y3)) != m.end())continue;
m[make_pair(x3,y3)] = 1;
printf("%lld %lld\n",x3,y3);
++cnt;
if(cnt == n / 10){
flag = 1;
break;
}
}
if(flag)break;
}
}
}
//1
//11
//0 0
//1 1
//2 3
//2 5
//0 10
//-2 10
//-5 9
//-8 7
//-8 4
//-6 1
//-2 0
\(T2\)
期望 \(DP\)……纯纯不会。
题解先放这，看看以后能不能看懂。
\(T3:\)
这个数据结构……过于逆天，还是放个题解先，看以后能不能懂。
