— Dark mode

Datatähti Open 2019

Function

  • Start: N/A
  • End: N/A
CSES - Datatähti Open 2019 - Results
Submission details
Task:Function
Sender:zscoder
Submission time:2019-01-18 09:28:28 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1details
#2ACCEPTED0.02 s1details
#3ACCEPTED0.02 s1details
#40.01 s1details
#5ACCEPTED0.05 s1details
#60.02 s1details
#70.02 s1details
#8ACCEPTED0.02 s1details
#90.04 s1details
#100.02 s2details
#11ACCEPTED0.02 s2details
#12ACCEPTED0.02 s2details
#130.03 s2details
#14ACCEPTED0.06 s2details
#150.07 s2details
#160.07 s2details
#170.06 s2details
#18ACCEPTED0.05 s2details
#19ACCEPTED0.06 s2details
#200.05 s2details
#210.02 s2details
#22ACCEPTED0.40 s2details
#230.42 s2details
#240.38 s2details
#25ACCEPTED0.47 s2details
#260.39 s2details
#270.41 s2details
#28ACCEPTED0.25 s2details
#290.31 s2details
#30ACCEPTED0.02 s2details
#31ACCEPTED0.02 s2details
#320.02 s2details
#330.01 s2details
#34ACCEPTED0.06 s2details
#35ACCEPTED0.47 s2details

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef ll coord_t;         // coordinate type
typedef ll coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2

struct Point {
	coord_t x, y;

	bool operator <(const Point &p) const {
		return x < p.x || (x == p.x && y < p.y);
	}
};

// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
	return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

int convex_hull(vector<Point> P)
{
	size_t n = P.size(), k = 0;
	if (n <= 3) return n;
	vector<Point> H(2*n);

	// Sort points lexicographically
	sort(P.begin(), P.end());

	// Build lower hull
	for (size_t i = 0; i < n; ++i) {
		while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}

	// Build upper hull
	for (size_t i = n-1, t = k+1; i > 0; --i) {
		while (k >= t && cross(H[k-2], H[k-1], P[i-1]) <= 0) k--;
		H[k++] = P[i-1];
	}

	H.resize(k-1);
	return H.size();
}

void solve()
{
	int n; cin>>n;
	vector<Point> vec;
	for(int i=0;i<n;i++)
	{
		int x,y; cin>>x>>y;
		Point p; p.x=x; p.y=y;
		vec.pb(p);
	}
	int res = convex_hull(vec);
	if(res==n) cout<<"YES\n";
	else cout<<"NO\n";
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin>>t;
	while(t--) solve();
}

Test details

Test 1

Group: 1

Verdict:

input
12
2
0 0
1 1
5
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
NO
NO
NO
YES
...
view save

Test 2

Group: 1

Verdict: ACCEPTED

input
100
2
92 30
22 44
2
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 3

Group: 1

Verdict: ACCEPTED

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 4

Group: 1

Verdict:

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
NO
YES
NO
NO
...
view save

Test 5

Group: 1

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 6

Group: 1

Verdict:

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 7

Group: 1

Verdict:

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 8

Group: 1

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 9

Group: 1

Verdict:

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

correct output
YES
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 10

Group: 2

Verdict:

input
13
2
0 0
1 1
5
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
NO
NO
NO
YES
...
view save

Test 11

Group: 2

Verdict: ACCEPTED

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 12

Group: 2

Verdict: ACCEPTED

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 13

Group: 2

Verdict:

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

correct output
YES
NO
YES
NO
NO
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 14

Group: 2

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 15

Group: 2

Verdict:

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

correct output
YES
YES
YES
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 16

Group: 2

Verdict:

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

correct output
NO
YES
YES
YES
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 17

Group: 2

Verdict:

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 18

Group: 2

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 19

Group: 2

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 20

Group: 2

Verdict:

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 21

Group: 2

Verdict:

input
13
2
0 0
1 1
5
...
view save

correct output
YES
YES
NO
YES
YES
...
view save

user output
YES
NO
NO
NO
YES
...
view save

Test 22

Group: 2

Verdict: ACCEPTED

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

correct output
NO
view save

user output
NO
view save

Test 23

Group: 2

Verdict:

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

correct output
YES
view save

user output
NO
view save

Test 24

Group: 2

Verdict:

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

correct output
YES
view save

user output
NO
view save

Test 25

Group: 2

Verdict: ACCEPTED

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

correct output
NO
view save

user output
NO
view save

Test 26

Group: 2

Verdict:

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

correct output
NO
YES
YES
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 27

Group: 2

Verdict:

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

correct output
YES
YES
NO
YES
YES
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 28

Group: 2

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 29

Group: 2

Verdict:

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

correct output
YES
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 30

Group: 2

Verdict: ACCEPTED

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 31

Group: 2

Verdict: ACCEPTED

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 32

Group: 2

Verdict:

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

correct output
NO
NO
NO
NO
YES
...
view save

user output
NO
YES
NO
YES
YES
...
view save

Test 33

Group: 2

Verdict:

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

correct output
NO
NO
YES
NO
NO
...
view save

user output
NO
NO
NO
NO
YES
...
view save

Test 34

Group: 2

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 35

Group: 2

Verdict: ACCEPTED

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

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Tasks

A Sum-B Bit string-C Sunset-D Binary tree-E Function-F Robot-G Classifier-

Submissions (zscoder)

4:23:34 03:15:18 453:11:40 453:08:56 453:07:57 03:04:17 453:03:54 03:02:17 453:01:24 452:55:51 02:46:04 02:38:09 452:37:11 452:35:10 452:34:37 02:32:14 452:29:20 452:28:14 452:26:42 452:25:40 452:03:36 01:59:10 01:49:53 00:47:14 00:42:17 0