题解 UVA11626 【Convex Hull】

珈乐唯毒 · 2021-03-05 22:25:58 · 题解

题意理解： 给出 n 个点，以其中 X-Y 排序最小的点为起点，逆时针输出其凸包的各顶点。

但是题目已经把凸包的顶点标好告诉你了，输入中最后带 Y 的就是顶点， N 的则不是。

所以直接照和最小点的斜率从小到大排序输出即可。

AC 代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;
struct Node{
    double x,y,k;
}node[N];
bool cmp(Node i,Node j){
    if(i.k==j.k)return i.y>j.y;
    return i.k<j.k;
}
int sn=1,sm;
int main(){
    int temm;
    scanf("%d",&temm);
    while(temm--){
        scanf("%d",&n);
        sm=0,sn=1;
        for(int i=1;i<=n;i++){
            double tx,ty;
            scanf("%lf%lf",&tx,&ty);
            char temp;
            cin>>temp;
            if(temp=='N')continue;
            node[++sm].x=tx,node[sm].y=ty;
            if(node[sm].x<node[sn].x)sn=sm;
            else if(node[sm].x==node[sn].x&&node[sm].y<node[sn].y)sn=sm;
        }
        node[0]=node[sn];
        for(int i=1;i<=sm;i++){
            double x=node[i].x-node[0].x;
            double y=node[i].y-node[0].y;
            if(x==0)node[i].k=1e8;
            else node[i].k=y/x;
        }
        sort(node+1,node+sm+1,cmp);
        printf("%d\n",sm);
        printf("%d %d\n",(int)node[0].x,(int)node[0].y);
        for(int i=1;i<=sm;i++)if(!(node[i].x==node[0].x&&node[0].y==node[i].y))printf("%d %d\n",(int)node[i].x,(int)node[i].y);
    }

    return 0;
}