QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#809802#9869. Horizon ScanningTDXIAORE 0ms4224kbC++202.2kb2024-12-11 17:29:092024-12-11 17:29:26

Judging History

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

  • [2024-12-11 17:29:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4224kb
  • [2024-12-11 17:29:09]
  • 提交

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(1.0 * y / x);
        } else if (y == 0) {
            return 0;
        } else {
            return 2*pi - atan(1.0 * (-y)/x);
        }
    } else if (x == 0) {
        if (y > 0) {
            return pi/2;
        } else {
            return pi*3/2;
        }
    } else {
        if (y > 0) {
            return pi - atan(1.0 * y / (-x));
        } else if (y == 0) {
            return pi;
        } else {
            return pi + atan(1.0 * (-y) /(-x));
        }
    }
}

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++) {
        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;
        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: 0ms
memory: 4224kb

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
Runtime Error

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.69299149748625166190
2.57486343606628764746
4.65275826725351926427
2.77263310738393675692
5.74276580690900217974
4.85769899102039204308
3.41989231259490455983
2.81279996208483895614
6.28318530717958712017
6.28318530717958712017
5.11728076666977305109
6.14678270277863880722
3.84208902353751913239
2...

result: