QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628666#7906. Almost ConvexxjunWA 223ms3720kbC++202.0kb2024-10-10 21:31:562024-10-10 21:32:01

Judging History

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

  • [2024-10-10 21:32:01]
  • 评测
  • 测评结果:WA
  • 用时:223ms
  • 内存:3720kb
  • [2024-10-10 21:31:56]
  • 提交

answer


#include<bits/stdc++.h>
using namespace std;
struct Point
{
	int x;
	int y;
	int f;
}d1[3005],d2[3005];
int vs[3005],st[3005],cnt,n;

int cha(Point a, Point b, Point c) {
	int xa = b.x - a.x;
	int ya = b.y - a.y;
	int xb = c.x - a.x;
	int yb = c.y - a.y;
	return yb * xa - ya * xb;
}
bool cmp1(Point a, Point b) {
	if (a.x == b.x) return a.y < b.y;
	else return a.x < b.x;
}

void TUBAO() {
	st[1] = 1; st[2] = 2; cnt = 2;
	for (int i = 3; i <= n; i++) {
	    while (cnt > 1 && cha(d1[st[cnt - 1]], d1[st[cnt]], d1[i]) <= 0) cnt--;
	    st[++cnt] = i;
	}
	st[++cnt] = n - 1;
	for (int i = n - 2; i >= 1; i--) {
	    while (cnt > 1 && cha(d1[st[cnt - 1]], d1[st[cnt]], d1[i]) <= 0) cnt--;
	    st[++cnt] = i;
	}
	--cnt;//最后会重复
}

int Cross(Point a, Point ots)
{
	return a.x * ots.y - a.y * ots.x;
}

int Quadrantt(Point a)//象限排序,注意包含四个坐标轴
{
	if (a.x > 0 && a.y >= 0)  return 1;
	if (a.x <= 0 && a.y > 0)  return 2;
	if (a.x < 0 && a.y <= 0)  return 3;
	if (a.x >= 0 && a.y < 0)  return 4;
	return 0;
}

bool cmp2(Point a, Point b)  //先按象限从小到大排序 再按极角从小到大排序
{
	if (Quadrantt(a) == Quadrantt(b))//返回值就是象限
		return Cross(a, b) < 0;//同一个象限计算叉乘   
	else return Quadrantt(a) < Quadrantt(b);
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> d1[i].x >> d1[i].y;
	sort(d1 + 1, d1 + 1 + n, cmp1);
	TUBAO();
	int ans = 1;//凸包算一个

	for (int i = 1; i <=cnt; i++) vs[st[i]] = 1;
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		if (vs[i]) continue;//只能选非凸包的点
		tot = 0;
		for (int j = 1; j <= n; j++) {
			if (j == i) continue;
			d2[++tot] = { d1[j].x - d1[i].x,d1[j].y - d1[i].y,0};
			if (vs[j]) d2[tot].f = 1;//打标记
		}
		sort(d2 + 1, d2 + 1 + n - 1, cmp2);
		for (int j = 1; j < n - 1; j++) {
			if (d2[j].f && d2[j + 1].f) ans++;
		}
		if (d2[n - 1].f && d2[1].f) ans++;
	}
	cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 223ms
memory: 3664kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

190994

result:

wrong answer 1st numbers differ - expected: '718', found: '190994'