背后的原因

发布时间:2021-05-12 10:37:56
贴主:FlyingLamb
热度:1

FlyingLamb 2021-05-12

#include<stdio.h>

#include<algorithm>

using namespace std;


struct Point {

    long long x, y;

    int num;

    Point(long long x = 0, long long y = 0) :x(x), y(y) { }//构造函数

}p[30001], ch[30001];

typedef Point Vector;


//向量 + 向量 = 向量

Vector operator + (Vector A, Vector B)

{

    return Vector(A.x + B.x, A.y + B.y);

}

//点 - 点 = 向量

Vector operator - (Point A, Point B)

{

    return Vector(A.x - B.x, A.y - B.y);

}

//向量 * 数 = 向量

Vector operator * (Vector A, long long p)

{

    return Vector(A.x * p, A.y * p);

}

//向量 / 数= 向量

Vector operator / (Vector A, double p)

{

    return Vector(A.x / p, A.y / p);

}


//比较

bool operator < (const Point& a, const Point& b)

{

    return a.x < b.x || (a.x == b.x && a.y < b.y);

}

//点乘

long long Dot(Vector A, Vector B)

{

    return A.x * B.x + A.y * B.y;

}

//叉乘

long long Cross(Vector A, Vector B)

{

    return A.x * B.y - B.x * A.y;

}


//计算凸包,输入点数组p,个数为p输出点数组ch,函数返回凸包顶点个数。

int ConvexHull(Point* p, int n, Point* ch)

{

    sort(p, p + n);

    int m = 0;

    for (int i = 0; i < n; ++i) {//下凸包

        //叉积<=0不是凸包边

        while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) < 0)m--;


        ch[m++] = p[i];

    }

    int k = m;

    for (int i = n - 2; i >= 0; --i) {//上凸包

        while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) < 0)m--;


        ch[m++] = p[i];

    }

    if (n > 1) m--;

    return m;

}

bool comp(Point a, Point b)

{

    return a.num < b.num;

}

int main()

{

    int n;

    scanf_s("%d", &n);///

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

    {

        scanf_s("%lld %lld", &p[i].x, &p[i].y);///(m=2)||

        p[i].num = i + 1;

    }

    int m = ConvexHull(p, n, ch);

    if(m<=2)

    {

        printf("-1");

        return 0;

    }

    //sort(ch, ch+ m-1,comp);

    //判共线

    if (0 == Cross(ch[0] - ch[1], ch[0] - ch[m - 1]))

        printf("-1");


    else

        for (int i = 0; i < m; ++i)

        {

            printf("%d ", ch[i].num);

        }

    return 0;

}

(0)

Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1