题解：UVA11626 Convex Hull

既然题目把哪些点在凸包上面都告诉你了，就不需要写个凸包上去了。

首先将 $x$ 坐标最小的点拎出来，从这个点开始逆时针考虑凸包上面每个条线段都是“左拐”，所以逆时针方向上的点与最小点连线的斜率是单调不降的。

直接将斜率拎出来排序，从小到大输出就可以了。$x$ 坐标为 $\displaystyle\min_{i=1}^{n} x_i$ 的按照 $y$ 坐标从大到小单独排序。

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int n,nx,ny,flag[N];
struct zyx{
    int x,y;
    char op;
}a[N];
bool cmp(zyx a,zyx b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
bool cmp1(zyx a,zyx b){
    double k1=(a.y-ny)*1.0/(a.x-nx),k2=(b.y-ny)*1.0/(b.x-nx);
    return k1<k2;
};
bool cmp2(zyx a,zyx b){return a.y>b.y;}
void sol(){
    cin>>n;
    vector<zyx> v,v2;
    v.clear(),v2.clear();
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y>>a[i].op;
    sort(a+1,a+1+n,cmp);
    nx=a[1].x,ny=a[1].y;
    for(int i=2;i<=n;i++){
        if(a[i].op=='Y'&&nx!=a[i].x)v.push_back(a[i]);
        else if(a[i].op=='Y')v2.push_back(a[i]);
    }
    sort(v.begin(),v.end(),cmp1);
    sort(v2.begin(),v2.end(),cmp2);
    cout<<1+v.size()+v2.size()<<'\n';
    cout<<nx<<" "<<ny<<'\n';
    for(int i=0;i<(int)v.size();i++)cout<<v[i].x<<" "<<v[i].y<<'\n';
    for(int i=0;i<(int)v2.size();i++)cout<<v2[i].x<<" "<<v2[i].y<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)sol();
    return 0;
}
```

正在渲染内容...