— Dark mode

Datatähti Open 2019

Function

  • Start: N/A
  • End: N/A
Submission details
Task:Function
Sender:SpeedOfMagic
Submission time:2019-01-19 18:23:18 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.01 s1details
#40.02 s1details
#5ACCEPTED0.06 s1details
#60.03 s1details
#70.02 s1details
#8ACCEPTED0.02 s1details
#90.01 s1details
#100.02 s2details
#11ACCEPTED0.02 s2details
#12ACCEPTED0.02 s2details
#130.02 s2details
#14ACCEPTED0.07 s2details
#150.07 s2details
#160.06 s2details
#170.07 s2details
#18ACCEPTED0.04 s2details
#19ACCEPTED0.04 s2details
#200.04 s2details
#210.02 s2details
#22ACCEPTED0.42 s2details
#230.43 s2details
#240.41 s2details
#25ACCEPTED0.49 s2details
#260.40 s2details
#270.42 s2details
#28ACCEPTED0.25 s2details
#290.33 s2details
#30ACCEPTED0.03 s2details
#31ACCEPTED0.03 s2details
#320.02 s2details
#330.02 s2details
#34ACCEPTED0.08 s2details
#35ACCEPTED0.45 s2details

Compiler report

input/code.cpp: In function 'bool cmp(pt, pt)':
input/code.cpp:37:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  return a.x < b.x || a.x == b.x && a.y < b.y;
                      ~~~~~~~~~~~^~~~~~~~~~~~

Code

/** MIT License Copyright (c) 2018-2019(!) Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
//code starts here
const int N = 1e6 + 1;
struct pt {
	int x, y;
};
v<pt> p;

bool cmp(pt a, pt b) {
	return a.x < b.x || a.x == b.x && a.y < b.y;
}

bool cw(pt a, pt b, pt c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool ccw(pt a, pt b, pt c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

void convex_hull (vector<pt> & a) {
	if (a.size() == 1)
        return;
	sort(a.begin(), a.end(), &cmp);
	pt p1 = a[0],  p2 = a.back();
	v<pt> up, down;
	up.pb(p1);
	down.pb(p1);
	rep(i, 1, sz(a)) {
		if (i == sz(a) - 1 || cw(p1, a[i], p2)) {
			while (sz(up) >= 2 && !cw(up[sz(up) - 2], up.back(), a[i]))
				up.pop_back();
			up.pb(a[i]);
		}
		if (i == sz(a) - 1 || ccw(p1, a[i], p2)) {
			while (down.size() >= 2 && !ccw (down[sz(down) - 2], down.back(), a[i]))
				down.pop_back();
			down.pb(a[i]);
		}
	}
	a.clear();
	rep(i, 0, sz(up))
		a.pb(up[i]);
	for (int i = down.size()-2; i; i--)
		a.pb(down[i]);
}

void run() {
    int t;
    get t;
    for (; t; t--) {
        int n;
        get n;
        p = v<pt>(n);
        rep(i, 0, n)
            read(p[i].x, p[i].y);
        convex_hull(p);
        if (sz(p) == n)
            put "YES";
        else
            put "NO";
        eol;
    }
}
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

Tasks

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

Submissions (SpeedOfMagic)

4:59:02 04:58:17 04:52:01 0