正文
CodeChef---- February Challenge 2018----Points Inside A Polygon
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
链接：https://www.codechef.com/FEB18/problems/POINPOLY
Points Inside A Polygon Problem Code: POINPOLY
You are given aconvex polygonwith N vertices.
You are given aconvex polygonwith N vertices.
You have to find any ⌊N/10⌋ distinct points with integer coordinates that lie strictly insidethe polygon, or determine that such a set of points doesn't exist.
Note: ⌊⌋ denotes the floor function, typically used in integer division.
Input
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of vertices of the polygon.
- The following N lines describe the vertices of the polygon in anticlockwise order. Each of these lines contains two space-separated integers x and y denoting the coordinates of one vertex.
Output
For each test case, if a valid set of points doesn't exist, print a single line containing the integer -1. Otherwise, print ⌊N/10⌋ lines. Each of these lines should contain two space-separated integers denoting the coordinates of one point.
The coordinates of all points should be integers with absolute value not exceeding 10 9 . If there are multiple solutions, you may print any one.
Constraints
- 1 ≤ T ≤ 10 5
- 10 ≤ N ≤ 10 5
- sum of N over all test cases ≤ 5 · 10 5
- |x|, |y| ≤ 10 9
- no three vertices of the polygon will be collinear
Subtasks
Subtask #1 (30 points): 1 ≤ T ≤ 100, 10 ≤ N ≤ 100
Subtask #2 (70 points): original constraints
Example
Input 1
11
0 0
1 1
2 3
2 5
0 10
-2 10
-5 9
-8 7
-8 4
-6 1
-2 0 Output 0 1
////////////////////////////////////////////////////////////
看到这道题是一脸懵逼的，后来想着在每个端点附近是有四个点，至少有一个点在凸包内，最多每三个点共享一个凸包内相邻点，于是肯定可以做
那么对于一个点，怎么判断是否在凸包内呢，我是把每个端点求出跟左右两点的直线方程式（o1求）然后先对于每一个端点，对于凸包的端点，判断是在每一条线的那一侧（根据方程式用正负值来表示）
（但是不可能n²来求得对每个点来说，凸包端点是在线的哪一侧，所以我去了最上下左右四个点，用于判断，只要四个点是不同的，肯定至少有一个点跟判定点不共线，就可以求得是在哪一侧，后来发现出bug了
就是当最上下左右四个点指向的是两个点的时候，代码是有bug的，错误的例子就是左下右上处在最上下左右，这时候需要特判一下，如果出现了，将相同的值换成另外一个其他点就行了）
然后对于某个端点相邻的点，求出他在两条线的哪一侧，如果跟凸包端点都相同，那就是在凸包内了，后来想着，几十个点围成一个宽为1的正方形不就gg了，所以还加了对于上下左右四个点是否也符合条件
（后来问了zk的做法之后，发现，原来凸包是没有三点共线的吗，，，emmm我好菜）（前面会出现那个地方会出bug也是因为加了上下左右点的判定，但是这四个点集中在两个点的话，如果两点相邻，那么他们的方向值就是 0 0，这样
任何点都会被判定成不符合）
然后贴个自己的代码
///////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define mst(a,b) memset((a),(b), sizeof a)
#define lowbit(a) ((a)&(-a))
#define IOS ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
typedef long long ll;
const int mod=1e9+;
const int maxn=1e5+;
int n;
struct point{int x,y;};
struct line{ll a,b,c;};
point po[maxn];
line li[maxn][];
int cc[maxn][];
int dx[]={,,-,},dy[]={,-,,};
vector<pair<int,int> >ans;
int up=1e5+,down=1e5+,le=1e5+,ri=1e5+;
void gtline(int i,int j,line& k){
k.a=po[i].y-po[j].y;
k.b=po[j].x-po[i].x;
k.c=(ll)po[i].x*po[j].y-(ll)po[j].x*po[i].y;
} int dir(line&k,int x,int y){
ll g=k.a*x+k.b*y+k.c;
if(g==)return ;
if(g<)return -;
return ;
}
bool gg(int p,int x,int y){
if(dir(li[p][],x,y)!=cc[p][])return true;
if(dir(li[p][],x,y)!=cc[p][])return true;
return false;
}
bool ok(int p,int x,int y){
if(gg(p,x,y))return false;
if(gg(le,x,y))return false;
if(gg(ri,x,y))return false;
if(gg(up,x,y))return false;
if(gg(down,x,y))return false;
return true;
}
void co(){
int ne=n/;
set<pair<int,int> >use;
vector<int>kk;
if(ans.size()<ne){printf("-1\n");return;}
for(int i=;i<ans.size();++i){
if(!use.count(ans[i])){
use.insert(ans[i]);
kk.push_back(i);
--ne;
if(!ne)break;
}
}
if(ne){printf("-1\n");return;}
for(int i=;i<kk.size();++i){
printf("%d %d\n",ans[kk[i]].first,ans[kk[i]].second);
} }
void check(){
if(up==ri||up==le){
int tmp=1e5+;
for(int i=;i<n;++i)if(i!=ri&&i!=le){
if(po[i].y>po[tmp].y)tmp=i;
}
up=tmp;
}
if(down==ri||down==le){
int tmp=1e5+;
for(int i=;i<n;++i)if(i!=ri&&i!=le){
if(po[i].y<po[tmp].y)tmp=i;
}
down=tmp;
}
}
int main(){
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
int t;scanf("%d",&t);
po[up].y=-1e9-;po[down].y=1e9+;po[le].x=1e9+;po[ri].x=-1e9-;
while(t--){
up=1e5+,down=1e5+,le=1e5+,ri=1e5+;
scanf("%d",&n);
for(int i=;i<n;++i){
scanf("%d%d",&po[i].x,&po[i].y);
if(po[i].x<po[le].x)le=i;
if(po[i].x>po[ri].x)ri=i;
if(po[i].y>po[up].y)up=i;
if(po[i].y<po[down].y)down=i;
}
check();
for(int i=;i<n;++i){
for(int j=;j<;++j){
int ad=(j==?-:);
gtline(i,(i+ad+n)%n,li[i][j]);cc[i][j]=;
cc[i][j]=dir(li[i][j],po[le].x,po[le].y);
if(!cc[i][j])
cc[i][j]=dir(li[i][j],po[ri].x,po[ri].y);
if(!cc[i][j])
cc[i][j]=dir(li[i][j],po[up].x,po[up].y);
if(!cc[i][j])
cc[i][j]=dir(li[i][j],po[down].x,po[down].y);
}
}
ans.clear();
for(int i=;i<n;++i){
for(int j=;j<;++j){
if(ok(i,po[i].x+dx[j],po[i].y+dy[j])){
ans.push_back(make_pair(po[i].x+dx[j],po[i].y+dy[j]));
break;
}
}
}
co();
}
return ;
}
zk 的做法是根据端点坐标的奇偶性分成四类，这样数量最多的一类至少有n/4个点（鸽笼原理），然后因为三点不共线，由于凸包每两个端点的中点一定在凸包内，或是在端点连线上（两点相邻）
由于三点不共线，所以，做多那个类以至少可以产出n/4-2个端点，这个极限情况只有当n==10可能出现，实际能够产出点应该是（n/4）²级别的（这是我猜的）
然后放一下根据zk的解法写的代码（瞬间短了很多）
//////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define mst(a,b) memset((a),(b), sizeof a)
#define lowbit(a) ((a)&(-a))
#define IOS ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
typedef long long ll;
const int mod=1e9+;
const int maxn=1e5+;
int x[maxn],y[maxn];
vector<int>has[][];
vector<pair<int,int> >ans;
set<pair<int,int> >uu;
int main(){
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
for(int i=;i<;++i)for(int j=;j<;++j)has[i][j].clear();
for(int i=;i<n;++i){
scanf("%d%d",&x[i],&y[i]);
has[abs(x[i])%][abs(y[i])%].push_back(i);
}
int a=,b=;
for(int i=;i<;++i)for(int j=;j<;++j)
if(has[i][j].size()>has[a][b].size())a=i,b=j;
int ne=n/; ans.clear(); uu.clear();
for(int i=;i<has[a][b].size();++i){
for(int j=i+;j<has[a][b].size();++j){
int l=has[a][b][i],r=has[a][b][j];
if(l+==r||l==&&r==n-)continue;
int mx=(x[l]+x[r])>>,my=(y[l]+y[r])>>;
if(!uu.count(make_pair(mx,my))){
ans.push_back(make_pair(mx,my));
uu.insert(make_pair(mx,my));
--ne;
}
if(!ne)break;
}
if(!ne)break;
}
for(int i=;i<ans.size();++i)printf("%d %d\n",ans[i].first,ans[i].second);
}
return ;
}
安慰一下自己emm我的代码比zk的多适用与正方性那种样例（非凸包）orz
