UVA11626 Convex Hull

· · 题解

\text{Description}

给出一些凸包上的点，要求你从 x 最小的点开始（x 相同时选择 y 最小的点），按逆时针顺序输出它们。

\text{Solution}

本题似乎用 Andrew 会更为方便，但蒟蒻还是喜欢简单清新的 Graham...
本题用 Graham 主要的麻烦就在于对凸包上共线的点如何处理。
这篇题解的做法是在共线时按照 y 降序排序，但是会被下面的数据 hack：
input:

1
4
0 0 Y
1 1 Y
2 2 Y
3 10 Y

ans：

4
0 0
1 1
2 2
3 10

output：

4
0 0
2 2
1 1
3 10

一个正确的做法是找到上下凸壳的分界点，然后下凸壳共线时按照距离升序排序，上凸壳共线时按照距离降序排序。
如果哪位有更好的实现欢迎评论或私信。

\text{Code}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

const double eps=1e-10;
const double pi=acos(-1.0);
struct V{
  double x,y;
  V():x(0),y(0){}
  V(double a,double b):x(a),y(b){}
};
inline void input(V &a){scanf("%lf%lf",&a.x,&a.y);}
void print(const V &a,int op=1){printf("%.10lf %.10lf",a.x,a.y);putchar(op?10:32);}
inline V operator + (const V &a,const V &b){return (V){a.x+b.x,a.y+b.y};}
inline V operator - (const V &a,const V &b){return (V){a.x-b.x,a.y-b.y};}
inline V operator * (const double &x,const V &a){return (V){a.x*x,a.y*x};}
inline V operator * (const V &a,const double &x){return (V){a.x*x,a.y*x};}
inline V operator / (const V &a,const double x){return (V){a.x/x,a.y/x};}
inline bool operator == (const V &a,const V &b){return abs(a.x-b.x)<eps&&abs(a.y-b.y)<eps;}
inline bool operator != (const V &a,const V &b){return !(a==b);}
inline double operator * (const V &a,const V &b){return a.x*b.x+a.y*b.y;}
inline double operator ^ (const V &a,const V &b){return a.x*b.y-a.y*b.x;}
inline double len(const V &a){return sqrt(a.x*a.x+a.y*a.y);}
inline bool operator < (const V &a,const V &b){
  return a.x<b.x-eps||(abs(a.x-b.x)<eps&&a.y<b.y-eps);
}

const int N=1e5+100;
const int M=505;
int n,m;
int top;
V p[N],zhan[N];

bool cmp(V a,V b){
    double d=((a-p[1])^(b-p[1]));
    if(abs(d)>eps) return d>0;
    else return len(a-p[1])<len(b-p[1]);
}
bool cmp2(V a,V b){
    double d=((a-p[1])^(b-p[1]));
    if(abs(d)>eps) return d>0;
    else return len(a-p[1])>len(b-p[1]);
}
void work(){
  n=read();m=0;
  V o;char c;
  for(int i=1;i<=n;i++){
    input(o);scanf(" %c",&c);
    if(c=='Y') p[++m]=o;
  }
  n=m;
  sort(p+1,p+1+n);
  sort(p+2,p+1+n,cmp);
  for(int i=2;i<n;i++){
    if(p[i+1].x<p[i].x){//找到分界点，后面重新排序 
        sort(p+i,p+1+n,cmp2);break;
    }
  }
  printf("%d\n",n);
  for(int i=1;i<=n;i++){
    printf("%.0lf %.0lf\n",p[i].x,p[i].y);
  }
}
signed main(){
#ifndef ONLINE_JUDGE
  //freopen("a.in","r",stdin);
  //freopen("a.out","w",stdout);
#endif
  int T=read();
  while(T--) work();
  return 0;
}
/*
1
4
0 0 Y
1 1 Y
2 2 Y
3 10 Y
*/