QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#809868#9869. Horizon ScanningO_startWA 110ms7508kbC++205.2kb2024-12-11 17:53:372024-12-11 17:53:38

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 17:53:38]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:7508kb
  • [2024-12-11 17:53:37]
  • 提交

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==k||!flag){
            cout<<setprecision(12)<<2.0*pi<<'\n';
            continue;
        }
        for(int i=1;i<=n;i++){
            int nxt=i+k;
            if(nxt>n){
                nxt=nxt%n;
            }
            double tmp=Angle(vertex[nxt],vertex[i]);
            //cout<<tmp<<'\n';
            //cout<<Cross(vertex[nxt],vertex[i])<<'\n';
            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: 1ms
memory: 7360kb

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: 110ms
memory: 7508kb

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'