SPOJ - #26 BSHEEP -建造围栏

Question

#include <bits/stdc++.h>
using namespace std;

#define EPS 1e-9

typedef double coord_t;
typedef double coord2_t;

struct point {
    double x, y;

    point(double _x, double _y)
    {
        x = _x, y = _y;
    }

    bool operator < (point p) const{
        if(fabs(x - p.x) > EPS)
            return x < p.x;
        return y < p.x;
    }
    bool operator == (point p) const{
        return fabs(x - p.x) < EPS && fabs (x - p.y) < EPS;
    }
};

coord2_t cross(const point &O, const point &A, const point &B)
{
    return (long)(A.x - O.x) * (B.y - O.y) - (long)(A.y - O.y) * (B.x - O.x);
}

bool cmp(point a, point b)
{
    if(fabs(a.y - b.y) > EPS)
        return a.y < b.y;
    return a.x < b.x;
}

vector<point> convex_hull(vector<point> P)
{
    int n = P.size();
    vector<point> H;

    sort(P.begin(), P.end(), cmp);

    for (int i = 0; i < n; ++i)
    {
        while(H.size() >= 2 && cross(H[H.size() - 2], H[H.size() - 1], P[i]) <= 0)
            H.pop_back();
        H.push_back(P[i]);
    }

    int l = H.size() + 1;
    for (int i = n - 1; i >= 0; i--)
    {
        while(H.size() >= l && cross(H[H.size() - 2], H[H.size() - 1], P[i]) <= 0)
            H.pop_back();
        H.push_back(P[i]);
    }
    return H;
}

int main()
{
    int tc, n, x, y;
    double length;
    vector<point> P;

    scanf("%d", &tc);

    while(tc--)
    {
        length = 0;
        P.clear();
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d %d", &x, &y);
            P.push_back(point(x, y));
        }

        P = convex_hull(P);

        for (int i = 0; i < (int) P.size() - 1; i++) {
            length += sqrt(pow((P[i].x - P[i+1].x),2) + pow((P[i].y - P[i+1].y),2));
        }
        printf("%.2lf\n", length);

        for (int i = 1; i < (int) P.size(); i++) {
            printf("%lf ", P[i]);      // Problem in this line , can't print the required output
        }
        printf("\n");

    }
    return 0;
}

这是一个凸包问题，我认为我做得很好，但不能输出p1 p2 .pk的问题。问题在于：

春天开始的时候，所有的羊都搬到了山上的更高的牧场。如果有成千上万的人，那就值得把他们聚集在一个地方。但是羊不喜欢离开他们的草地。帮助牧羊人，给他筑一个篱笆，围住所有的羊。篱笆的长度应该尽可能小！假设羊是小得可怜的，而且它们不动。有时有几只羊站在同一个地方。如果只有一只羊，它可能就要死了，所以根本不需要栅栏. 输入 T测试<= 100的次数 N羊数<= 100000 第一只羊的x1 y1坐标..。辛恩 整数坐标为-10000至10000 其他绵羊名单 分组的文本不会出现在输入文件中。假设羊是按输入顺序编号的。 输出 圆周长度，2位精度 p1 p2 ..。pk站在篱笆角上的羊；第一只应该放在最底部，尽量向左，其余的应该按逆时针顺序写；忽略所有站在同一地方的羊，但第一只出现在输入文件中；绵羊的数量应该是最小的。 下一步解决方案

Answer 1

在结构中，在保持点的位置的同时，再添加一个变量。

struct point {
    double x, y, c;

    point(double _x, double _y, double _c)
    {
        x = _x, y = _y,c = _c;
    }

    bool operator < (point p) const{
        if(fabs(x - p.x) > EPS)
            return x < p.x;
        return y < p.x;
    }
    bool operator == (point p) const{
        return fabs(x - p.x) < EPS && fabs (x - p.y) < EPS;
    }
};

当您接受输入时，将所有三种输入都推回去：

for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        P.push_back(point(x, y,i+1));
     }