— Dark mode

Datatähti 2019 loppu

Funktio

  • Start: 2019-01-17 12:00:00
  • End: 2019-01-17 17:00:00
Submission details
Task:Funktio
Sender:Olli Järviniemi
Submission time:2019-01-17 16:27:21 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.02 s1details
#2ACCEPTED0.02 s1details
#3ACCEPTED0.01 s1details
#40.02 s1details
#5ACCEPTED0.05 s1details
#60.03 s1details
#70.02 s1details
#8ACCEPTED0.03 s1details
#90.03 s1details
#100.02 s2details
#11ACCEPTED0.03 s2details
#12ACCEPTED0.02 s2details
#130.02 s2details
#14ACCEPTED0.05 s2details
#150.07 s2details
#160.06 s2details
#170.06 s2details
#18ACCEPTED0.05 s2details
#19ACCEPTED0.05 s2details
#200.04 s2details
#210.01 s2details
#22ACCEPTED0.48 s2details
#230.43 s2details
#240.42 s2details
#25ACCEPTED0.51 s2details
#260.44 s2details
#270.47 s2details
#28ACCEPTED0.26 s2details
#290.35 s2details
#30ACCEPTED0.02 s2details
#31ACCEPTED0.03 s2details
#320.02 s2details
#330.02 s2details
#34ACCEPTED0.07 s2details
#35ACCEPTED0.47 s2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:86:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < bo.size(); ++j) {
                        ~~^~~~~~~~~~~
input/code.cpp:104:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < bo.size(); ++j) {
                        ~~^~~~~~~~~~~

Code

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int ,int> pii;
typedef long long ll;

const double INF = 1e9;

bool big(pii a, pii b) {
    int fi = a.first*b.second;
    int se = a.second*b.first;
    if(se > fi) return false;
    return true;
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    for(int abba = 1; abba <= t; ++abba) {
        int n;
        cin >> n;
        vector<pii> v;
        for(int i = 1; i <= n; ++i) {
            int x, y;
            cin >> x >> y;
            v.push_back({x, y});
        }
        
        if(n <= 3) {
            cout << "YES\n";
            continue;
        }
//        vector<pair<pii, pii> > bo;
        vector<pair<double, double> > bo;
        for(int i = 1; i < n-1; ++i) {
            int x0 = v[i-1].first;
            int y0 = v[i-1].second;
            
            int x1 = v[i].first;
            int y1 = v[i].second;
            
            int x2 = v[i+1].first;
            int y2 = v[i+1].second;
            
           // pii k01 = {y1 - y0, x1 - x0};
           // pii k12 = {y2 - y1, x2 - x1};
            double k01;
            if(x1 == x0) {
                k01 = INF;
            } else {
                k01 = (double) (y1 - y0)/(x1 - x0);
            }
            
            double k12;
            if(x1 == x2) {
                k12 = INF;
            } else {
                k12 = (double) (y2 - y1)/(x2 - x1);
            }
            if(k01 >= 0 && k12 >= 0) {
                bo.push_back({min(k01, k12), max(k01, k12)}); //Think of these as angles
            }
            if(k01 < 0 && k12 >= 0) {
                bo.push_back({max(k01, k12), min(k01, k12)}); //Think of these as angles
            }
            if(k12 < 0 && k01 >= 0) {
                bo.push_back({max(k01, k12), min(k01, k12)}); //Think of these as angles
            }
            if(k12 < 0 && k01 < 0) {
                bo.push_back({min(k01, k12), max(k01, k12)}); //Think of these as angles
            }
            //First spot contains lower bounds, second one contains upper bounds
        }
        
        sort(bo.begin(), bo.end());
        //Find the angle that's the smallest upper bound
        
        double up = bo[0].second;
        for(int j = 0; j < bo.size(); ++j) {
            if(up >= 0) {
                if(bo[j].second < 0) continue;
                if(bo[j].second < up) {
                    up = bo[j].second;
                }
            } else {
                if(bo[j].first > 0) {
                    up = bo[j].second;
                } else {
                    up = max(up, bo[j].second);
                }
            }
        }
        
        //Find the greatest lower bound
        
        double low = 0;
        for(int j = 0; j < bo.size(); ++j) {
            double t = bo[j].first;
            if(low < 0) {
                if(t >= 0) continue;
                if(t > low) low = t;
            } else {
                if(t < 0) {
                    low = t;
                } else {
                    low = max(low, t);
                }
            }
        }
      //  cout << "\n";
       // cout << "Test case : " << abba << ". UP and LOW: " << up << " " << low << "\n";
        
        if(low >= 0) {
            if(up < 0) {
                cout << "YES\n";
            } else {
                if(up > low) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        } else {
            if(up > 0) {
                cout << "NO\n";
            } else {
                if(up <= low) {
                    cout << "NO\n";
                } else {
                    cout << "YES\n";
                }
            }
        }
    }
}

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
YES
YES
YES
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
NO
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
YES
YES
YES
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
NO
YES
NO
NO
NO
...
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
YES
YES
YES
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
NO
YES
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
YES
NO
NO
YES
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 Summa-B Bittijono-C Auringonlasku-D Binääripuu-E Funktio-F Robotti-G Luokittelija-

Submissions (Olli Järviniemi)

2019-01-17 16:32:46 02019-01-17 16:27:21 0