CSES - Datatähti Open 2019 - Results
Submission details
Task:Function
Sender:tutis
Submission time:2019-01-19 19:26:41
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED45
#2ACCEPTED55
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.02 s1details
#4ACCEPTED0.02 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.02 s1details
#7ACCEPTED0.03 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.01 s1details
#10ACCEPTED0.02 s2details
#11ACCEPTED0.02 s2details
#12ACCEPTED0.03 s2details
#13ACCEPTED0.01 s2details
#14ACCEPTED0.07 s2details
#15ACCEPTED0.08 s2details
#16ACCEPTED0.07 s2details
#17ACCEPTED0.07 s2details
#18ACCEPTED0.06 s2details
#19ACCEPTED0.05 s2details
#20ACCEPTED0.04 s2details
#21ACCEPTED0.01 s2details
#22ACCEPTED0.53 s2details
#23ACCEPTED0.48 s2details
#24ACCEPTED0.48 s2details
#25ACCEPTED0.58 s2details
#26ACCEPTED0.50 s2details
#27ACCEPTED0.55 s2details
#28ACCEPTED0.29 s2details
#29ACCEPTED0.39 s2details
#30ACCEPTED0.02 s2details
#31ACCEPTED0.02 s2details
#32ACCEPTED0.02 s2details
#33ACCEPTED0.03 s2details
#34ACCEPTED0.07 s2details
#35ACCEPTED0.53 s2details

Code

/*input
2
4
0 0
2 1
3 -1
2 -2
4
0 0
2 1
3 -1
2 0
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll modulo = (1000000000) + 7;
struct poll
{
	ll x, y;
	poll()
	{
		x = 5;
		y = 6;
	}
	poll(ll x, ll y): x(x), y(y)
	{

	}
	ll ketv()
	{
		if (x == 0 && y == 0)
			return 0;
		if (y == 0 && x > 0)
			return 1;
		if (y > 0 && x > 0)
			return 2;
		if (y > 0 && x == 0)
			return 3;
		if (y > 0 && x < 0)
			return 4;
		if (y == 0 && x < 0)
			return 5;
		if (y < 0 && x < 0)
			return 6;
		if (y < 0 && x == 0)
			return 7;
		return 8;
	}
};
poll operator-(poll a, poll b)
{
	return poll(a.x - b.x, a.y - b.y);
}
poll operator*(poll a, poll b)
{
	return poll(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
ll cross(poll a, poll b)
{
	return (a.x * b.y - a.y * b.x);
}
bool vienodi(poll a, poll b)
{
	if (cross(a, b) != 0)
		return false;
	if (a.x * b.x < 0 || a.y * b.y < 0)
		return false;
	return true;
}
void rask(poll a, poll b, poll c, poll d, poll &L, poll &R, bool &ok)
{
	if (vienodi(a, c))
		return;
	if (vienodi(b, d))
		return;
	if (cross(a, c) < 0 && cross(c, b) < 0)
	{
		L = c;
		R = b;
		return;
	}
	if (cross(a, d) < 0 && cross(d, b) < 0)
	{
		L = a;
		R = d;
		return;
	}
	ok = false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	ll T;
	cin >> T;
	while (T--)
	{
		ll n;
		cin >> n;
		poll a[n];
		for (ll i = 0; i < n; i++)
			cin >> a[i].x >> a[i].y;
		poll b[n - 1];
		for (ll i = 0; i < n - 1; i++)
			b[i] = a[i + 1] - a[i];
		sort(b, b + (n - 1), [](poll a, poll b) {
			if (a.ketv() != b.ketv())
				return a.ketv() < b.ketv();
			return cross(a, b) > 0;
		});
		vector<poll>CHECK;
		poll x[9];
		for (ll i = 0; i < (n - 1); i++)
		{
			x[b[i].ketv()] = b[i];
		}
		for (ll i = 0; i < 9; i++)
		{
			CHECK.push_back(x[i]);
		}
		for (ll i = n - 2; i >= 0; i--)
		{
			x[b[i].ketv()] = b[i];
		}
		for (ll i = 0; i < 9; i++)
		{
			CHECK.push_back(x[i]);
		}
		bool gerai = false;
		for (poll a : CHECK)
		{
			bool ok = true;
			for (poll i : b)
			{
				if (cross(i, a) > 0)
					ok = false;
				if (cross(i, a) == 0 && !vienodi(i, a))
					ok = false;
			}
			if (ok)
			{
				gerai = true;
				break;
			}
		}
		if (gerai)
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
12
2
0 0
1 1
5
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 2

Group: 1

Verdict: ACCEPTED

input
100
2
92 30
22 44
2
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 3

Group: 1

Verdict: ACCEPTED

input
100
3
-55 -98
-59 -55
-2 88
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 4

Group: 1

Verdict: ACCEPTED

input
100
4
87 81
-84 42
18 -46
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 5

Group: 1

Verdict: ACCEPTED

input
100
1000
-81 38
92 -21
-10 -65
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 6

Group: 1

Verdict: ACCEPTED

input
100
110
-99 -9
-98 -9
-96 -8
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 7

Group: 1

Verdict: ACCEPTED

input
100
78
-100 95
-99 96
-98 95
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 8

Group: 1

Verdict: ACCEPTED

input
100
201
-100 97
-100 96
-99 99
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 9

Group: 1

Verdict: ACCEPTED

input
100
45
-100 89
-100 90
-97 90
...

correct output
YES
NO
NO
NO
NO
...

user output
YES
NO
NO
NO
NO
...

Test 10

Group: 2

Verdict: ACCEPTED

input
13
2
0 0
1 1
5
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 11

Group: 2

Verdict: ACCEPTED

input
100
2
-517113909 -39540276
-209411537 -831819487
2
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 12

Group: 2

Verdict: ACCEPTED

input
100
3
-991349544 139282777
646238126 16140762
-4488261 817588303
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 13

Group: 2

Verdict: ACCEPTED

input
100
4
891187584 -889373775
-453505448 -469134344
-683807769 8725517
...

correct output
YES
NO
YES
NO
NO
...

user output
YES
NO
YES
NO
NO
...

Test 14

Group: 2

Verdict: ACCEPTED

input
100
1000
-866614983 -994037153
775605588 -328510132
390868551 927606059
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 15

Group: 2

Verdict: ACCEPTED

input
100
1000
-911073332 -1000000000
-905159999 -1000000000
-904949593 -999999999
...

correct output
YES
YES
YES
NO
NO
...

user output
YES
YES
YES
NO
NO
...

Test 16

Group: 2

Verdict: ACCEPTED

input
100
1000
-1000000000 950042028
-946551105 -1000000000
-940508390 -1000000000
...

correct output
NO
YES
YES
YES
NO
...

user output
NO
YES
YES
YES
NO
...

Test 17

Group: 2

Verdict: ACCEPTED

input
100
1000
-949977239 -1000000000
-948279892 -1000000000
-947497811 -999999999
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 18

Group: 2

Verdict: ACCEPTED

input
100
806
-899 -1000
-898 -1000
-896 -999
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 19

Group: 2

Verdict: ACCEPTED

input
100
777
-1000 914
-1000 915
-999 916
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 20

Group: 2

Verdict: ACCEPTED

input
100
775
-999 998
-995 -1000
-994 -1000
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 21

Group: 2

Verdict: ACCEPTED

input
13
2
0 0
1 1
5
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 22

Group: 2

Verdict: ACCEPTED

input
1
999748
-995394098 -1000000000
-995392159 -1000000000
-995386584 -999999999
...

correct output
NO

user output
NO

Test 23

Group: 2

Verdict: ACCEPTED

input
1
1000000
-954368893 -1000000000
-954366895 -1000000000
-954364896 -999999999
...

correct output
YES

user output
YES

Test 24

Group: 2

Verdict: ACCEPTED

input
1
1000000
-1000000000 928772368
-1000000000 928772506
-999999999 928772642
...

correct output
YES

user output
YES

Test 25

Group: 2

Verdict: ACCEPTED

input
1
999754
-901705699 -1000000000
-901702695 -1000000000
-901702062 -999999999
...

correct output
NO

user output
NO

Test 26

Group: 2

Verdict: ACCEPTED

input
100
10000
-1000000000 919783772
-918885599 -1000000000
-918825263 -1000000000
...

correct output
NO
YES
YES
NO
NO
...

user output
NO
YES
YES
NO
NO
...

Test 27

Group: 2

Verdict: ACCEPTED

input
10
99998
-997024120 -77018772
-997011201 -77017738
-996986132 -77015834
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 28

Group: 2

Verdict: ACCEPTED

input
100
7934
-10000 9905
-10000 9906
-9999 9906
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 29

Group: 2

Verdict: ACCEPTED

input
100
9710
-99754 -6983
-99786 -6055
-99751 -6548
...

correct output
YES
NO
NO
NO
NO
...

user output
YES
NO
NO
NO
NO
...

Test 30

Group: 2

Verdict: ACCEPTED

input
100
2
802396401 -641287652
30956766 -527704723
2
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 31

Group: 2

Verdict: ACCEPTED

input
100
3
755025461 -953536159
-402145543 137775005
-700733185 821755784
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 32

Group: 2

Verdict: ACCEPTED

input
100
4
-673213071 571383249
-963633735 -859013318
-591788323 791136643
...

correct output
NO
NO
NO
NO
YES
...

user output
NO
NO
NO
NO
YES
...

Test 33

Group: 2

Verdict: ACCEPTED

input
100
5
-124483012 623794901
233757283 -234519096
-987338502 737259422
...

correct output
NO
NO
YES
NO
NO
...

user output
NO
NO
YES
NO
NO
...

Test 34

Group: 2

Verdict: ACCEPTED

input
100
1000
154383911 872030445
-9594726 190227899
908758769 -9615631
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 35

Group: 2

Verdict: ACCEPTED

input
100
10000
642800667 -694556052
-343795089 -341227394
800920828 676674460
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...