gym 101164 H.Pub crawl 凸包

时间：2023-03-10 07:17:32
gym 101164 H.Pub crawl 凸包

题目链接：http://codeforces.com/gym/101164/attachments

题意：对于已知的 n 个二维坐标点，要求按照某种特定的连线方式将尽可能多的点连接（任意相邻的 3 个点 a , b , c ，点 c 必须在有向线段 ab 的左侧。问最多可以连多少点，并给出连线顺序。

思路：因为连接最多的点，尽量让形成一个凸包将点包起来，形成螺旋式的连接所有的点，凸包模板；

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

#include<stdlib.h>

#include<time.h>

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e5+,M=1e6+,inf=;

const LL INF=1e18+,mod=;

const double eps = 1e-;

const double PI = acos(-1.0);

int sgn(double x)

{

    if(fabs(x) < eps)return ;

    if(x < )return -;

    else return ;

}

struct Point

{

    double x,y;

    int pos;

    Point() {}

    Point(double _x,double _y)

    {

        x = _x;

        y = _y;

    }

    Point operator -(const Point &b)const

    {

        return Point(x - b.x,y - b.y);

    }

    //叉积

    double operator ^(const Point &b)const

    {

        return x*b.y - y*b.x;

    }

//点积

    double operator *(const Point &b)const

    {

        return x*b.x + y*b.y;

    }

}a[N];

double dist(Point a,Point b)

{

    return sqrt((a-b)*(a-b));

}

int n;

const int MAXN = ;

Point listt[MAXN];

int Stack[MAXN],top,vis[N]; //相对于listt[0]的极角排序

vector<int>ans;

bool _cmp(Point p1,Point p2)

{

    double tmp = (p1-listt[])^(p2-listt[]);

    if(sgn(tmp) > )return true;

    else if(sgn(tmp) ==  && sgn(dist(p1,listt[]) - dist(p2,listt[])) <= ) return true;

    else return false;

}

void Graham()

{

    Point p0;

    int k = ;

    p0 = listt[]; //找最下边的一个点

    for(int i = ; i < n; i++)

    {

        if( (p0.y > listt[i].y) || (p0.y == listt[i].y && p0.x > listt[i].x) )

        {

            p0 = listt[i];

            k = i;

        }

    }

    swap(listt[k],listt[]);

    sort(listt+,listt+n,_cmp);

    int m=;

    Stack[] = ;

    Stack[] = ;

    vis[]=;

    vis[]=;

    top = ;

    while(top<n)

    {

        for(int i = ; i < n; i++)

        {

            if(vis[i])continue;

            while(top >  && sgn((listt[Stack[top-]]-listt[Stack[top-]])^(listt[i]-listt[Stack[top-]])) <= )

            top--,vis[Stack[top]]=;

            Stack[top++] = i;

            vis[i]=;

        }

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++)

        scanf("%lf%lf",&listt[i].x,&listt[i].y),listt[i].pos=i+;

    Graham();

    printf("%d\n",n);

    for(int i=;i<n;i++)

        printf("%d ",listt[Stack[i]].pos);

    return ;

}

/*

5

0 4

3 0

7 11

9 1

13 8

*/

相关文章