Task: | Function |
Sender: | tasmeemreza |
Submission time: | 2019-01-18 13:34:25 +0200 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1 | details |
#2 | ACCEPTED | 0.02 s | 1 | details |
#3 | ACCEPTED | 0.03 s | 1 | details |
#4 | ACCEPTED | 0.02 s | 1 | details |
#5 | ACCEPTED | 0.04 s | 1 | details |
#6 | WRONG ANSWER | 0.02 s | 1 | details |
#7 | WRONG ANSWER | 0.03 s | 1 | details |
#8 | ACCEPTED | 0.03 s | 1 | details |
#9 | WRONG ANSWER | 0.02 s | 1 | details |
#10 | ACCEPTED | 0.01 s | 2 | details |
#11 | ACCEPTED | 0.01 s | 2 | details |
#12 | ACCEPTED | 0.02 s | 2 | details |
#13 | ACCEPTED | 0.02 s | 2 | details |
#14 | ACCEPTED | 0.06 s | 2 | details |
#15 | WRONG ANSWER | 0.05 s | 2 | details |
#16 | WRONG ANSWER | 0.06 s | 2 | details |
#17 | WRONG ANSWER | 0.04 s | 2 | details |
#18 | WRONG ANSWER | 0.04 s | 2 | details |
#19 | WRONG ANSWER | 0.03 s | 2 | details |
#20 | WRONG ANSWER | 0.04 s | 2 | details |
#21 | ACCEPTED | 0.02 s | 2 | details |
#22 | WRONG ANSWER | 0.29 s | 2 | details |
#23 | ACCEPTED | 0.29 s | 2 | details |
#24 | ACCEPTED | 0.28 s | 2 | details |
#25 | ACCEPTED | 0.27 s | 2 | details |
#26 | WRONG ANSWER | 0.26 s | 2 | details |
#27 | WRONG ANSWER | 0.27 s | 2 | details |
#28 | ACCEPTED | 0.16 s | 2 | details |
#29 | WRONG ANSWER | 0.22 s | 2 | details |
#30 | ACCEPTED | 0.01 s | 2 | details |
#31 | ACCEPTED | 0.02 s | 2 | details |
#32 | ACCEPTED | 0.02 s | 2 | details |
#33 | WRONG ANSWER | 0.01 s | 2 | details |
#34 | ACCEPTED | 0.04 s | 2 | details |
#35 | ACCEPTED | 0.28 s | 2 | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 2; i < v.size(); i++) { ~~^~~~~~~~~~ input/code.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 3; i < v.size(); i++) { ~~^~~~~~~~~~ input/code.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ~~~~~^~~~~~~~~~ input/code.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%lld %lld", &a[i].x, &a[i].y); ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp: In function 'int main(int, const char**)': input/code.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with...
Code
#include "bits/stdc++.h" using namespace std; struct Point { long long x, y; Point (long long x, long long y) : x(x), y(y) {} Point () {} Point operator + (Point p) { return Point(x + p.x, y + p.y); } Point operator - (Point p) { return Point(x - p.x, y - p.y); } } a[1000010]; long long cross(Point p, Point q) { return p.x * q.y - q.x * p.y; } // Given three colinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true; return false; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(Point p, Point q, Point r) { // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ // for details of below formula. long long val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // colinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true; // Special Cases // p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and q2 are colinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; // Doesn't fall in any of the above cases } bool inside(Point a, Point b, Point c) { long long A = abs(cross(a, b)); long long B = abs(cross(c, a - c)) + abs(cross(c, b - c)) + abs(cross(a - c, b - c)); if(A == B) return true; if(doIntersect(a, b, c, Point(0, 0))) return true; return false; } bool bad[1000010]; void solve() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lld %lld", &a[i].x, &a[i].y); bad[i] = false; } vector <Point> v; for(int i = 2; i < n; i++) { if(cross(a[i - 1] - a[i], a[i + 1] - a[i]) == 0) { if(!onSegment(a[i - 1], a[i], a[i + 1])) { printf("NO\n"); return ; } bad[i] = true; } } for(int i = 2; i <= n; i++) { if(a[i - 1].x == a[i].x && a[i - 1].y == a[i].y) { bad[i - 1] = true; } } for(int i = 1; i <= n; i++) { if(!bad[i]) { v.emplace_back(a[i]); } } for(int i = 2; i < v.size(); i++) { assert(cross(v[i - 1] - v[i - 2], v[i] - v[i - 2]) != 0); } for(int i = 3; i < v.size(); i++) { if(inside(v[i - 1] - v[i - 2], v[i] - v[i - 1], v[i - 3] - v[i - 2])) { printf("NO\n"); return ; } } printf("YES\n"); } int main(int argc, char const *argv[]) { int t; scanf("%d", &t); while(t--) { solve(); } return 0; }
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 ... Truncated |
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 ... Truncated |
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 ... Truncated |
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 ... Truncated |
Test 6
Group: 1
Verdict: WRONG ANSWER
input |
---|
100 110 -99 -9 -98 -9 -96 -8 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
YES NO NO NO NO ... Truncated |
Test 7
Group: 1
Verdict: WRONG ANSWER
input |
---|
100 78 -100 95 -99 96 -98 95 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
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 ... Truncated |
Test 9
Group: 1
Verdict: WRONG ANSWER
input |
---|
100 45 -100 89 -100 90 -97 90 ... |
correct output |
---|
YES NO NO NO NO ... |
user output |
---|
YES NO YES NO YES ... Truncated |
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 ... Truncated |
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 ... Truncated |
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 ... Truncated |
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 ... Truncated |
Test 15
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 1000 -911073332 -1000000000 -905159999 -1000000000 -904949593 -999999999 ... |
correct output |
---|
YES YES YES NO NO ... |
user output |
---|
YES YES YES YES YES ... Truncated |
Test 16
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 1000 -1000000000 950042028 -946551105 -1000000000 -940508390 -1000000000 ... |
correct output |
---|
NO YES YES YES NO ... |
user output |
---|
NO YES YES YES NO ... Truncated |
Test 17
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 1000 -949977239 -1000000000 -948279892 -1000000000 -947497811 -999999999 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... Truncated |
Test 18
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 806 -899 -1000 -898 -1000 -896 -999 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 19
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 777 -1000 914 -1000 915 -999 916 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO YES NO NO NO ... Truncated |
Test 20
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 775 -999 998 -995 -1000 -994 -1000 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO YES NO NO ... Truncated |
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: WRONG ANSWER
input |
---|
1 999748 -995394098 -1000000000 -995392159 -1000000000 -995386584 -999999999 ... |
correct output |
---|
NO |
user output |
---|
YES |
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: WRONG ANSWER
input |
---|
100 10000 -1000000000 919783772 -918885599 -1000000000 -918825263 -1000000000 ... |
correct output |
---|
NO YES YES NO NO ... |
user output |
---|
NO YES YES YES NO ... Truncated |
Test 27
Group: 2
Verdict: WRONG ANSWER
input |
---|
10 99998 -997024120 -77018772 -997011201 -77017738 -996986132 -77015834 ... |
correct output |
---|
YES YES NO YES YES ... |
user output |
---|
YES YES YES 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 ... Truncated |
Test 29
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 9710 -99754 -6983 -99786 -6055 -99751 -6548 ... |
correct output |
---|
YES NO NO NO NO ... |
user output |
---|
YES NO NO NO NO ... Truncated |
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 ... Truncated |
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 ... Truncated |
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 ... Truncated |
Test 33
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 5 -124483012 623794901 233757283 -234519096 -987338502 737259422 ... |
correct output |
---|
NO NO YES NO NO ... |
user output |
---|
NO NO YES NO NO ... Truncated |
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 ... Truncated |
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 ... Truncated |