QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276592#7906. Almost ConvexstarcatWA 420ms3628kbC++172.8kb2023-12-05 23:29:312023-12-05 23:29:32

Judging History

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

  • [2023-12-05 23:29:32]
  • 评测
  • 测评结果:WA
  • 用时:420ms
  • 内存:3628kb
  • [2023-12-05 23:29:31]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;
const int N = 2e3 + 10;
typedef pair<int, int> PII;

PII operator+ (PII a, PII b) { return {a.x + b.x, a.y + b.y}; }
PII operator- (PII a, PII b) { return {a.x - b.x, a.y - b.y}; }
PII operator* (PII a, int t) { return {a.x * t, a.y * t}; }
PII operator/ (PII a, int t) { return {a.x / t, a.y / t}; } 
int operator* (PII a, PII b) { return a.x * b.y - a.y * b.x; }
int operator& (PII a, PII b) { return a.x * b.x + a.y * b.y; }
int cross(PII a, PII b)  { return a.x * b.y - b.x * a.y; }
int area(PII a, PII b, PII c) { return (b - a) * (c - a); }

PII q[N], qq[N];
int n, stk[N];
bool use[N];//判断该点是否用过,用于求下凸包时使用
map<PII, bool> mp;

bool qua_up(PII a) { //求在上半部分还是下半部分
	if(a.y > 0 || (a.y == 0 && a.x >= 0)) return true;
	return false;
}

//下面排序略微慢一点
void psort(PII dots[], PII c = {0, 0}) {
	sort(dots, dots + n, [&](PII a, PII b) {
		if(a == c) return true;
		if(qua_up(a - c) != qua_up(b - c)) return qua_up(a - c) > qua_up(b - c);
		else return (a - c) * (b - c) > 0;
	});
}

void andrew() {
    sort(q, q + n);
    int top = 0;
    for(int i = 0; i < n; i ++ ) {
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0){ //精度问题判断大小正负时要用函数
            if (area(q[stk[top - 1]], q[stk[top]], q[i]) < 0)
                use[stk[top -- ]] = false;
            else top -- ;
        }
        stk[++ top] = i;
        use[i] = true;
    }

    use[0] = false; //重新判断一次起点
    for(int i = n - 1; i >= 0; i -- ) {
        if(use[i]) continue;
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) 
            top --;
        stk[++ top] = i;
    }

    for(int i = 1; i <= top; i ++ ) mp[q[stk[i]]] = 1;
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;
    andrew();
	for(int i = 0; i < n; i ++ ) qq[i] = q[i];
	// for(int i = 0; i < n; i ++ )
	// 	if(mp[q[i]] == 1) cout << q[i].x << ' ' << q[i].y << '\n';
	// cout << "--------------\n";
	int res = 1;
	for(int i = 0; i < n; i ++ ) 
		if(mp[qq[i]] != 1) {
			//cout << "qq:" << qq[i].x << ' ' << qq[i].y << '\n';
			psort(q, qq[i]); //备份好的点在qq中
			// for(int j = 0; j < n; j ++ )
			// 	cout << q[j].x << ' ' << q[j].y << '\n';
			int f = 0;
			for(int j = 0; j < n; j ++ ) {
				if(mp[q[j]] == 1) f ++;
				else f = 0;
				if(f >= 2) res ++;
			}
			//判断最后一个点和第一个点
			if(mp[q[1]] == 1 && f) res ++;
			//cout << "cur_res:" << res << '\n';
		}
	cout << res << '\n';
}

int main() {
    int T = 1;
    //cin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: 420ms
memory: 3556kb

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:

104949

result:

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