QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#809724#9869. Horizon ScanningTDXIAOWA 27ms4256kbC++202.5kb2024-12-11 16:57:582024-12-11 16:58:00

Judging History

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

  • [2024-12-11 16:58:00]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:4256kb
  • [2024-12-11 16:57:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const double pi = acos(-1);

struct Point{
	ll x, y;
    Point(){}
    Point(ll _x, ll _y){x = _x, y=_y;}
};
int operator^(const Point &a, const Point &b){
	return a.x * b.y - a.y * b.x;	
}
int quad(const Point &a){
	if(a.x > 0 && a.y == 0){
		return 1;
	}else if(a.x > 0 && a.y > 0){
		return 2;
	}else if(a.x == 0 && a.y > 0){
		return 3;
	}else if(a.x < 0 && a.y > 0){
		return 4;
	}else if(a.x < 0 && a.y == 0){
		return 5;
	}else if(a.x < 0 && a.y < 0){
		return 6;
	}else if(a.x == 0 && a.y < 0){
		return 7;
	}else if(a.x > 0 && a.y < 0){
		return 8;
	}
}

bool cmp(const Point &a, const Point &b){
	int qa = quad(a), qb = quad(b);
	if(qa != qb){
		return qa < qb;
	}else{
		return (a ^ b) > 0;
	}
}

double fun(Point p) {
    auto [x, y] = p;
    if (x > 0) {
        if (y > 0) {
            return atan(y/x);
        } else if (y == 0) {
            return atan(y/x);
        } else {
            return atan(x/(-y)) + pi*3/2;
        }
    } else if (x == 0) {
        if (y > 0) {
            return pi/2;
        } else {
            return pi*3/2;
        }
    } else {
        if (y > 0) {
            return atan((-x)/y) + pi/2;
        } else if (y == 0) {
            return pi;
        } else {
            return pi + pi/2 - atan((-x)/(-y));
        }
    }
}

void solve() {
    int n, k;
    cin>>n>>k;
    vector<Point> a(2*n+1);
    for (int i = 1; i <= n; i++) {
        ll x, y;
        cin>>x>>y;
        a[i] = {x, y};
    }
    sort(a.begin()+1, a.begin()+n+1, cmp);
    // for (int i = 1; i <= n; i++) {
    //     printf("x = %lld, y = %lld\n", a[i].x, a[i].y);
    // }
    // printf("\n");
    // cout<<fun(Point(1, -1))<<'\n';
    // cout<<fun(Point(2, -1))<<'\n';
    for (int i = 1; i <= n; i++) {
        a[i+n] = a[i];
    }
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        double l = fun(a[i]);
        double r = fun(a[i+k]);
        if (i+k > n) r += 2*pi;
        // printf("i = %d, l = %lf, r = %lf, f = %lf\n", i, l, r, r-l);
        ans = max(ans, r-l);
    }
    cout<<fixed<<setprecision(20);
    cout<<ans<<'\n';
}

int main()
{
    if (ifstream("test.in")) {
        freopen("test.in", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4152kb

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.28318530717958623200
1.57079632679489655800
5.49778714378213795300
3.14159265459155179201
3.14159265358979311600

result:

ok 5 numbers

Test #2:

score: -100
Wrong Answer
time: 27ms
memory: 4256kb

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:

2.35619449019234483700
2.35619449019234483700
4.95736764351155390074
3.14159265358979311600
5.49778714378213884117
4.85769899102039204308
3.92699081698724139500
3.46334320798643524597
6.28318530717958623200
6.28318530717958712017
5.49778714378213795300
6.28318530717958712017
3.60524026259059926502
2...

result:

wrong answer 1st numbers differ - expected: '1.6929915', found: '2.3561945', error = '0.3917344'