QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#809883 | #9869. Horizon Scanning | O_start | WA | 106ms | 7536kb | C++20 | 5.4kb | 2024-12-11 18:02:50 | 2024-12-11 18:03:00 |
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-10;
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{
double x, y;
Point(double xx = 0, double 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;
bool flag=0;
for(int i=2;i<=n;i++){
if(vertex[i]==vertex[1]){
continue;
}
else{
flag=1;
break;
}
}
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(vertex[nxt]==vertex[i]&&flag){
ans=max(ans,2*pi);
continue;
}
if(dcmp(Cross(vertex[nxt],vertex[i]))==1){
ans=max(ans,2*pi-tmp);
}
else ans=max(ans,tmp);
}
cout<<setprecision(12)<<ans<<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7332kb
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 3.14159265359
result:
ok 5 numbers
Test #2:
score: -100
Wrong Answer
time: 106ms
memory: 7536kb
input:
10000 16 1 -10 -6 -5 -6 -4 9 -2 5 -2 10 1 -7 1 -5 1 6 3 1 4 -9 6 -10 6 -3 6 1 8 -5 8 -4 9 -4 17 4 -9 2 -8 -4 -8 -3 -8 -1 -6 -2 -6 -1 -6 8 -5 -8 -5 10 -4 8 -2 -8 4 -9 4 0 5 -3 8 -5 9 -2 10 10 10 6 -7 2 -4 6 -2 -7 -2 -1 -1 7 1 -9 1 8 3 -4 7 -4 9 -2 14 3 -9 10 -8 -10 -8 -8 -6 -7 -6 -5 -1 -7 -1 -2 0 -1 ...
output:
1.69299149749 2.57486343607 4.65275826725 2.77263310738 5.74276580691 4.85769899102 3.41989231259 2.81279996208 6.28318530718 6.28318530718 5.11728076667 6.14678270278 3.84208902354 2.34249671682 3.46334320799 6.28318530718 5.96143475278 3.32470347085 5.26277492806 5.67245934279 1.67387793532 1.1141...
result:
wrong answer 42nd numbers differ - expected: '6.2831853', found: '6.2599337', error = '0.0037006'