CSES - Datatähti Open 2019 - Results
Submission details
Task:Function
Sender:tasmeemreza
Submission time:2019-01-18 13:32:45
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.02 s1details
#3ACCEPTED0.02 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.04 s1details
#60.03 s1details
#70.02 s1details
#8ACCEPTED0.03 s1details
#90.02 s1details
#10ACCEPTED0.02 s2details
#11ACCEPTED0.02 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.01 s2details
#14ACCEPTED0.05 s2details
#150.04 s2details
#160.04 s2details
#170.05 s2details
#180.04 s2details
#190.04 s2details
#200.04 s2details
#21ACCEPTED0.01 s2details
#220.28 s2details
#23ACCEPTED0.28 s2details
#24ACCEPTED0.29 s2details
#25ACCEPTED0.26 s2details
#260.26 s2details
#270.26 s2details
#28ACCEPTED0.16 s2details
#290.20 s2details
#30ACCEPTED0.02 s2details
#31ACCEPTED0.02 s2details
#32ACCEPTED0.01 s2details
#330.02 s2details
#34ACCEPTED0.06 s2details
#35ACCEPTED0.26 s2details

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 = 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:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~

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

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:

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

correct output
NO
NO
NO
NO
NO
...

user output
YES
NO
NO
NO
NO
...

Test 7

Group: 1

Verdict:

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:

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

correct output
YES
NO
NO
NO
NO
...

user output
YES
NO
YES
NO
YES
...

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:

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

correct output
YES
YES
YES
NO
NO
...

user output
YES
YES
YES
YES
YES
...

Test 16

Group: 2

Verdict:

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:

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:

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:

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

correct output
NO
NO
NO
NO
NO
...

user output
NO
YES
NO
NO
NO
...

Test 20

Group: 2

Verdict:

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

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
YES
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:

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:

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

correct output
NO
YES
YES
NO
NO
...

user output
NO
YES
YES
YES
NO
...

Test 27

Group: 2

Verdict:

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

Test 29

Group: 2

Verdict:

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:

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