QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#809691#9869. Horizon ScanningTDXIAOWA 1ms4128kbC++202.3kb2024-12-11 16:46:382024-12-11 16:46:40

Judging History

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

  • [2024-12-11 16:46:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4128kb
  • [2024-12-11 16:46:38]
  • 提交

answer

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

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

struct Point{
	ll x, 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 atan((-x)/(-y)) + pi;
        }
    }
}

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(), 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");
    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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4128kb

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
2.35619449019234483700
5.49778714378213795300
4.71238897938293099799
3.14159265358979311600

result:

wrong answer 2nd numbers differ - expected: '1.5707963', found: '2.3561945', error = '0.5000000'