Submission #3788226
Source Code Expand
//https://www.luogu.org/problemnew/show/P2742
//凸包边长
#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 = 1;
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:105: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
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_max.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt |
Case Name |
Status |
Exec Time |
Memory |
00_max.txt |
TLE |
2103 ms |
256 KB |
00_sample_01.txt |
AC |
1 ms |
256 KB |
00_sample_02.txt |
AC |
1 ms |
256 KB |
00_sample_03.txt |
AC |
1 ms |
256 KB |
00_sample_04.txt |
TLE |
2103 ms |
256 KB |
00_sample_05.txt |
TLE |
2103 ms |
256 KB |
01_rnd_00.txt |
AC |
1 ms |
256 KB |
01_rnd_01.txt |
AC |
1 ms |
256 KB |
01_rnd_02.txt |
AC |
1 ms |
256 KB |
01_rnd_03.txt |
AC |
1 ms |
256 KB |
01_rnd_04.txt |
AC |
1 ms |
256 KB |
01_rnd_05.txt |
AC |
1 ms |
256 KB |
01_rnd_06.txt |
AC |
1 ms |
256 KB |
01_rnd_07.txt |
AC |
1 ms |
256 KB |
01_rnd_08.txt |
AC |
1 ms |
256 KB |
01_rnd_09.txt |
AC |
1 ms |
256 KB |
01_rnd_10.txt |
AC |
1 ms |
256 KB |
01_rnd_11.txt |
AC |
1 ms |
256 KB |
01_rnd_12.txt |
AC |
1 ms |
256 KB |
01_rnd_13.txt |
AC |
1 ms |
256 KB |
01_rnd_14.txt |
AC |
1 ms |
256 KB |
01_rnd_15.txt |
AC |
1 ms |
256 KB |
01_rnd_16.txt |
AC |
1 ms |
256 KB |
01_rnd_17.txt |
AC |
1 ms |
256 KB |
01_rnd_18.txt |
AC |
1 ms |
256 KB |
01_rnd_19.txt |
AC |
1 ms |
256 KB |