QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234656#5538. Magical Barrierdmmm#WA 1ms3728kbC++202.5kb2023-11-01 20:27:362023-11-01 20:27:36

Judging History

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

  • [2023-11-01 20:27:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3728kb
  • [2023-11-01 20:27:36]
  • 提交

answer

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

#define int long long
const int N = 1e3 + 7;
typedef struct Vector {
	int x,y;
	int id;
	Vector operator - (Vector &oth) {
		return {x - oth.x , y - oth.y};
	}
	int dot (Vector &oth) {
		return oth.x * x + y * oth.y;
	}
	int cross (Vector &oth) {
		return oth.y * x - y * oth.x;
	}
	bool operator < (const Vector&oth) const {
		return x < oth.x || (x==oth.x && y < oth.y);
	}
} point;
bool ban[N];
point dick;
int direc (point a,point b,point c) {
	Vector x = b - a;
	Vector y = c - b;
	return x.cross (y);
}
bool ccw (point a,point b,point c) {
	return direc (a , b, c) > 0;
}
bool cw (point a,point b,point c) {
	return direc (a , b  , c) < 0;
}
void convex_hull (vector<point> &a) {
	sort (a .begin() ,a .end());
	vector<point> up , down;
	point first = a[0] , last = a.back();
	up.push_back (first);
	down.push_back (first);
	dick = first;
	int p = a.size() - 1;
	for (int i=1;i<(int ) a.size();i++) {
		if (i==p || cw (first , a[i] , last)) {
			while (up.size() >=2 && !cw (up[(int) up.size() - 2] , up.back() , a[i])) up.pop_back ();
			up.push_back (a[i]);
		}
		if (i==p || ccw (first , a[i] , last)) {
			while (down.size() >=2 && !ccw (down[(int) down.size() - 2] , down.back() , a[i])) down.pop_back ();
			down.push_back (a[i]);
		}
	}
	a.clear();
	for (point &i : up) {
		a.push_back (i);
		ban[i.id] = 1;
	
	}
	for (int i=(int) down.size() - 2;i >= 1;i--) {
		a.push_back (down[i]);
		ban[down[i].id] = 1;
	}
	
}

int n;
point a[N];
vector<point> b;
point x[N * 2];
int cal (int l, int r) {
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++) {
		if (i==x[l].id || i==x[r].id) {
			continue;
		}
		if (ccw (x[l], a[i], x[r])) {
			cnt1++;
		}
		else {
			cnt2++;
		}
	}
	return cnt1 * cnt2;
}
signed main () {
	ios::sync_with_stdio (false);
	cin.tie(0);
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
		b.push_back (a[i]);
	}
	
	if (n <= 2) {
		cout << 0;
		return 0;
	}
	convex_hull (b);
	for (int i = 0; i < (int) b.size(); i++) {
		x[i] = x[i + (int)b.size()] = b[i];
	}
	int res = 0;
	int op = 1;
	int m = b.size();
//	cout << m << endl;
	for (int i = 0; i < m; i++) {
		for (int j = op; j < m + i; j++) {
			if (j == m + i - 1) {
				op = m + i - 1;
				break;
			}
			else if (cal (i, j) > cal (i, j + 1)){
				op = j;
				break;
			}
		}
		res = max (res, cal (i, op));
	}
	cout << res;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

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

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

2
0 0
0 1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

4
-3 0
3 0
0 3
0 1

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

4
0 0
0 1
1 0
1 1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

2
0 -1337
-5 -4

output:

0

result:

ok single line: '0'

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3728kb

input:

1000
496963365 -584310020
963238159 -571008004
18078662 -750762438
135156509 -968440195
77520950 -725908810
956053561 -538228505
806742035 -803854232
529068738 -825479182
64371444 -975013392
164324947 -824966981
629969244 -744727107
685160229 -787078273
985061882 -907085223
349370979 -716383138
4759...

output:

0

result:

wrong answer 1st lines differ - expected: '248984', found: '0'