QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812424 | #9869. Horizon Scanning | Time_South | WA | 1ms | 7420kb | C++20 | 5.3kb | 2024-12-13 15:20:57 | 2024-12-13 15:20:58 |
Judging History
answer
#pragma oucGCC optimize(2)
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<stack>
#include<map>
#include<unordered_map>
#include<iomanip>
using namespace std;
const int maxn = 200005;
#define ll long long
const long long inf = 0xfffffffffffffff;
const long long mod = 998244353;
int t;
const double eps = 1e-6;
const double pi = acos(-1);
int xx, yy;
int dcmp(double a) {
if (fabs(a) < eps)
{
return 0;
}
return a < 0 ? -1 : 1;
}
struct Point {
ll x, y;
Point(ll xx = 0, ll yy = 0) : x(xx), y(yy) {}
};//点的构造
typedef Point Vector;
Point vertex[maxn];//储存凸包中的点
Vector operator - (Point p1, Point p2) {
return Vector(p2.x - p1.x, p2.y - p1.y);
}
Vector operator + (Point p1, Point p2) {
return Vector(p2.x + p1.x, p2.y + p1.y);
}
bool operator ==(Point p1, Point p2) {
return dcmp(p1.x - p2.x) == 0 && dcmp(p1.y - p2.y) == 0;
}
Vector operator * (Point A, double p) {
return Vector(A.x * p, A.y * p);
}
Vector operator / (Point A, double p) {
return Vector(A.x / p, A.y / p);
}
double Dis(Point A, Point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}//计算两点之间距离
double Dot(Vector A, Vector B) {
return A.x * B.x + A.y * B.y;
} //向量点乘
double Length(Vector A) {
return sqrt(Dot(A, A));
} //向量长度
double Angle(Vector A, Vector B) {
return acos(Dot(A, B) / Length(A) / Length(B));
} //向量夹角
double Cross(Vector v1, Vector v2) {
return v1.x * v2.y - v1.y * v2.x;
}//向量叉乘
double DistanceToSegment(Point P, Point A, Point B) {
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if (dcmp(Dot(v1, v2)) < 0) {
return Length(v2);
}
else if (dcmp(Dot(v1, v3)) > 0) {
return Length(v3);
}
else {
return fabs(Cross(v1, v2)) / Length(v1);
}
}//计算点P到线段AB的距离
bool cmp_x(Point A, Point B) {
if (A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
bool cmp2(Point A, Point B) {
if (atan2(A.y - yy, A.x - xx) != atan2(B.y - yy, B.x - xx))
return (atan2(A.y - yy, A.x - xx)) < (atan2(B.y - yy, B.x - xx));
return A.x < B.x;
}//极角排序
int n, k;
bool isConvex(vector<Point>& p) {
int n = p.size();
if (dcmp(Cross(p[n - 1] - p[0], p[1] - p[0]) >= 0)) {
return false;
}
if (dcmp(Cross(p[n - 2] - p[n - 1], p[0] - p[n - 1]) >= 0)) {
return false;
}
for (int i = 1; i < n - 1; i++) {
if (dcmp(Cross(p[i - 1] - p[i], p[i + 1] - p[i])) >= 0) {
return false;
}
}
return true;
}//多边形凹凸性判断
double area(vector<Point>& p) {
int n = p.size();
double res = 0.0;
for (int i = 0; i < n - 1; i++) {
res += Cross(p[i] - p[0], p[i + 1] - p[0]);
}
return res / 2;
}//多边形面积计算
int ConvexHull(vector<Point>& p) {
int n = p.size();
memset(vertex, 0, sizeof(vertex));
sort(p.begin(), p.end(), cmp_x);
vertex[0] = p[0];
xx = vertex[0].x;
yy = vertex[0].y;
sort(p.begin() + 1, p.end(), cmp2);
vertex[1] = p[1];
int top = 1;
for (int i = 2; i < n; i++)
{
while (i >= 1 && Cross(vertex[top] - vertex[top - 1], p[i] - vertex[top - 1]) <= 0)
top--;
vertex[++top] = p[i];//控制<0或<=0可以控制重点,共线的,具体视题目而定。
}
return top;
}//获取凸包顶点
double ConvexHullPerimeter(vector<Point>& p) {
int m = ConvexHull(p);
double ans = 0.0;
for (int i = 0; i < m; i++)
ans += Dis(vertex[i], vertex[i + 1]);
ans += Dis(vertex[m], vertex[0]);
return ans;
}//计算凸包周长
double ConvexHullArea(vector<Point>& p) {
int m = ConvexHull(p);
double ans = 0.0;
vertex[m] = vertex[0];
for (int i = 0; i < m; i++) {
ans += (vertex[i].x * vertex[i + 1].y - vertex[i + 1].x * vertex[i].y);
}
ans = ans / 2;
return ans;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while (t--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> vertex[i].x >> vertex[i].y;
}
sort(vertex + 1, vertex + n + 1, cmp2);
// for(int i=1;i<=n;i++){
// vertex[i+n]=vertex[i];
// }
double ans = 0.0;
if (n == 1 || n == k) {
cout << setprecision(12) << 2 * pi << '\n';
continue;
}
for (int i = 1; i <= n; i++) {
int nxt = i + k;
bool flag = 0;
if (nxt > n) {
nxt = nxt - n;
flag = 1;
}
double tmp = Angle(vertex[nxt], vertex[i]);
//cout<<tmp<<" "<<flag<<'\n';
//cout<<Cross(vertex[nxt],vertex[i])<<'\n';
if (dcmp(tmp) == 0 && flag) {
ans = max(ans, 2 * pi);
continue;
}
if (dcmp(Cross(vertex[nxt], vertex[i])) == 1 || dcmp(Cross(vertex[nxt], vertex[i])) == 0) {
ans = max(ans, 2 * pi - tmp);
}
else ans = max(ans, tmp);
}
cout << setprecision(12) << ans << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7420kb
input:
5 1 1 0 1 8 2 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1 4 2 -1 1 0 1 0 2 1 1 4 2 -1000000000 0 -998244353 1 998244353 1 1000000000 0 3 1 0 1 0 2 0 -1
output:
6.28318530718 1.57079632679 5.49778714378 3.14159265359 6.28318530718
result:
wrong answer 5th numbers differ - expected: '3.1415927', found: '6.2831853', error = '1.0000000'