Submission #3788213

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef pair<double, double> Point;

//精度判断
const double eps = 1e-10;
int dcmp(double x)
{
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
//计算叉积，小于0说明p1在p2的逆时针方向(右边)，即p0p1的极角大于p0p2的极角
double cross(const Point& p0, const Point& p1, const Point& p2)
{
    return (p1.first - p0.first)*(p2.second - p0.second) - (p2.first - p0.first)*(p1.second - p0.second);
}
//计算距离
double dis(const Point& p1, const Point& p2)
{
    return sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second));
}

//记录最下面的点，用于排序
Point pp;

bool cmp(const Point &p1, const Point &p2)
{
    double temp = cross(pp, p1, p2);
    if (temp == 0)//极角相等按照距离从小到大排序
    {
        return dis(pp, p1) < dis(pp, p2);
    }
    return temp > 0;
}

vector<Point> graham_scan(vector<Point>& p)
{
    vector<Point> ch;
    int n = p.size();
    //点数小于2时，线段或者点
    if (n <= 2)
    {
        return p;
    }
    int top = 2;
    int index = 0;
    //选出Y坐标最小的点，若Y坐标相等，选择X坐标小的点
    for (int i = 1; i < n; ++i)
    {
        if (p[i].second < p[index].second || (p[i].second == p[index].second && p[i].first < p[index].first))
        {
            index = i;
        }
    }
    swap(p[0], p[index]);
    ch.push_back(p[0]);
    pp = p[0];
    //按极角排序
    sort(p.begin() + 1, p.end(), cmp);
    ch.push_back(p[1]);
    ch.push_back(p[2]);
    for (int i = 3; i < n; ++i)
    {
        while (top > 0 && cross(ch[top - 1], p[i], ch[top]) >= 0)
        {
            --top;
            ch.pop_back();
        }
        ch.push_back(p[i]);
        ++top;
    }
    return ch;
}
//卡壳
double rotatingCalipers(const vector<Point>&p)
{
    int q = 2;
    double ans = 0;
    int n = p.size();
    for (int i = 0; i < n; i++)
    {
        //叉乘的模长等于组成的平行四边形面积，所以用来找到距离一条边最远的点
        while (cross(p[i], p[(i + 1) % n], p[(q + 1) % n]) > cross(p[i], p[(i + 1) % n], p[q]))
            q = (q + 1) % (n);
        ans = max(ans, max(dis(p[i], p[q]), dis(p[(i + 1) % n], p[q])));
    }
    return ans;
}

int main()
{
    int n;
    double x, y;
    while (~scanf("%d", &n))
    {
        vector<Point>p;
        for (int i = 0; i < n; i++)
        {
            scanf("%lf%lf", &x, &y);
            p.emplace_back(x, y);
        }
        printf("%.6lf", rotatingCalipers(graham_scan(p)));
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:103:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lf%lf", &x, &y);
                                    ^

Judge Result