QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341121#7730. Convex CheckerYansuan_HCl#WA 1ms3652kbC++141.3kb2024-02-29 15:55:482024-02-29 15:55:48

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-02-29 15:55:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3652kb
  • [2024-02-29 15:55:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { char GC; x = 0; bool f = 0;
	for (; !IC; GC) if (c == '-') f = 1;
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define U(i,l,r) for(int i(l),END##i(r); i<=END##i; ++i)
#define D(i,l,r) for(int i(l),END##i(r); i>=END##i; --i)
#define ms(x, v) memset(x, v, sizeof(x))
#define meow(...) fprintf(stderr, __VA_ARGS__)
using ll = long long;

const int N = 200005;
#define x real()
#define y imag()
using P = complex<ll>;
P p[N]; int n;

int main() {
	// freopen("arrebol.in", "r", stdin);

	rd(n);
	U (i, 1, n) {
		ll a, b; rd(a, b);
		p[i] = {a, b};
	}
	sort(p + 1, p + n + 1, [&](const P &l, const P &r) {
		return l.x == r.x ? l.y < r.y : l.x < r.x;
	});
	U (i, 2, n) if (p[i] == p[i - 1]) {
		puts("No");
		exit(0);
	}

	D (i, n, 1) p[i] -= p[1];
	sort(p + 1, p + n + 1, [&](const P &l, const P &r) {
		ll cx = l.x * r.y - l.y * r.x;
		if (cx == 0) return l.x < r.x;
		return cx < 0;
	});
	p[n + 1] = p[1];
	int stk[N] {}, sp = 2; stk[1] = 1, stk[2] = 2;
	U (i, 3, n + 1) {
		P p1 = p[stk[sp]] - p[stk[sp - 1]], p2 = p[i] - p[stk[sp]];
		if (p1.x * p2.y - p1.y * p2.x >= 0) {
			puts("No");
			exit(0);
		}
		stk[++sp] = i;
	}
	puts("Yes");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

Yes

result:

ok answer is YES

Test #4:

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3548kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES