QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80551#5538. Magical BarrierXKErrorWA 3ms3960kbC++2.4kb2023-02-24 11:05:032023-02-24 11:05:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-24 11:05:04]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3960kb
  • [2023-02-24 11:05:03]
  • 提交

answer

#include <bits/stdc++.h>

#define maxn 2005
#define db double

using namespace std;

const db pi = acos(-1);

int n;
struct node {
	int x, y;
	
	int &operator [](int d) {
		return d ? y : x;
	}
	
	node operator +(node a) {
		return {x + a.x, y + a.y};
	}
	
	node operator -(node a) {
		return {x - a.x, y - a.y};
	}
	
	db ag() {
		return atan2(y, x);
	}
}a[maxn];

int id[maxn];
db w[maxn][maxn];
db t[maxn][maxn];
int cc[maxn];
int sm[maxn][maxn];

int qry(int x, db y) {
	return sm[x][lower_bound(w[x] + 1, w[x] + n, y) - w[x] - 1];
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			t[i][j] = (a[j] - a[i]).ag();
		}
	}
	for (int i = 1; i <= n; i++) {
		int m = 0;
		for (int j = 1; j <= n; j++) if (i ^ j) id[++m] = j;
		sort(id + 1, id + n, [&](int x, int y) {return t[i][x] < t[i][y];});
		for (int j = 1; j < n; j++) id[++m] = id[j], w[i][m] = (w[i][j] = t[i][id[j]]) + 2 * pi;
		m /= 2;
		for (int op = 1, rp = 1; op < n; op++) {
//			int j = id[op];
			while (w[i][rp + 1] < w[i][op] + pi) ++rp;
//			cout<<i<<" "<<j<<" "<<id[rp]<<" "<<w[op]<<" "<<w[rp]<<endl;
			cc[op] += rp - op;
			cc[op + 1] -= rp - op;
			cc[op + 1] -= 1;
			cc[rp + 1] += 1;
			
			cc[rp + 1] += 1;
			cc[op + m] -= 1;
			cc[op + m] -= op + m - rp - 1;
			cc[op + m + 1] += op + m - rp - 1;
		}
		m *= 2;
		
		for (int i = 1; i <= m; i++) cc[i] += cc[i - 1];
		for (int i = 1; i <= m; i++) cc[i] += cc[i - 1];
		m /= 2;
		for (int j = 1; j < n; j++) sm[i][j] = (cc[j] + cc[j + m]) / 2;
		for (int j = 1; j <= m * 2; j++) cc[j] = 0;
//		for (int j = 1; j <= m; j++) cout<<sm[i][j]<<" ";
//		puts("");
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int m = 0;
		for (int j = 1; j <= n; j++) if (i ^ j) id[++m] = j;
		sort(id + 1, id + n, [&](int x, int y) {return t[i][x] < t[i][y];});
		for (int j = 1; j < n; j++) id[++m] = id[j];
		m /= 2;
		for (int op = 1, rp = 1; op < n; op++) {
//			int j = id[op];
			while (w[i][rp + 1] < w[i][op] + pi) ++rp;
			int rs = rp - op;
			int ls = op + m - rp - 1;
			int res = rs * ls;
			int du = qry(id[op], t[i][id[op]]);
			int dd = qry(i, t[id[op]][i]);
//			cout<<i<<" "<<id[op]<<" "<<res<<" "<<du<<" "<<dd<<" "<<res - du - dd<<endl;
			ans = max(ans, res - du - dd);
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*
5
2 3
2 1
1 5
3 7
5 4
*/

詳細信息

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 3960kb

input:

6
0 0
0 6
6 0
6 6
1 4
1 2

output:

4

result:

wrong answer 1st lines differ - expected: '3', found: '4'