QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628724#7906. Almost ConvexxjunWA 274ms3732kbC++203.1kb2024-10-10 21:56:242024-10-10 21:56:25

Judging History

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

  • [2024-10-10 21:56:25]
  • 评测
  • 测评结果:WA
  • 用时:274ms
  • 内存:3732kb
  • [2024-10-10 21:56:24]
  • 提交

answer

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

struct Point
{
	int x;
	int y;
	int f;
}d1[3005],d2[3005],O,P;
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);
}


struct D {
	int x, y;
}d[3005];
inline bool cmp(D A, D B) { return (A.x == B.x) ? (A.y < B.y) : (A.x < B.x); }
//struct D1 {
//	int x, y, id;
//}d1[3005];
#define D1 Point

D1 operator - (D1 A, D1 B) { return { A.x - B.x,A.y - B.y,0 }; }
int operator ^ (D1 A, D1 B) { return A.x * B.y - B.x * A.y; }
inline bool cmp_vec(D1 A, D1 B) {
	if (((P - O) ^ (A - O)) == 0 && (P.x - O.x) * (A.x - O.x) > 0) return 1;
	if (((P - O) ^ (B - O)) == 0 && (P.x - O.x) * (B.x - O.x) > 0) return 0;
	if ((((P - O) ^ (A - O)) > 0) != (((P - O) ^ (B - O)) > 0)) return ((P - O) ^ (A - O)) > ((P - O) ^ (B - O));
	return ((A - O) ^ (B - O)) > 0;
}

signed 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,vs[j]};
	//		//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++;
	//}
	int tot = 0;
	for (int u = 1; u <= n; u++) {
		if (vs[u]) continue;
		tot = 0;
		for (int i = 1; i <= n; i++) if (i != u) d2[++tot] = { d1[i].x,d1[i].y,vs[i] };
		O = { d1[u].x,d1[u].y,0 }; P = { O.x - 1,O.y,0 };
		sort(d2 + 1, d2 + tot + 1, cmp_vec);

		if (d2[1].f && d2[tot].f) ans++;
		for (int i = 1; i < tot; i++) if (d2[i].f && d2[i + 1].f) ans++;
	}
	cout << ans << "\n";
	return 0;
}

详细

Test #1:

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

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: 3728kb

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: 0ms
memory: 3656kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 3664kb

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: 274ms
memory: 3660kb

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:

190026

result:

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