— Dark mode

Datatähti Open 2019

Function

  • Start: N/A
  • End: N/A
  • Contest has ended
CSES - Datatähti Open 2019 - Results
Submission details
Task:Function
Sender:bogdan10bos
Submission time:2019-01-20 14:03:02 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.02 s1details
#2ACCEPTED0.03 s1details
#30.02 s1details
#40.01 s1details
#5ACCEPTED0.03 s1details
#60.03 s1details
#70.01 s1details
#8ACCEPTED0.02 s1details
#90.02 s1details
#100.02 s2details
#11ACCEPTED0.02 s2details
#120.02 s2details
#130.02 s2details
#14ACCEPTED0.04 s2details
#150.04 s2details
#160.05 s2details
#170.04 s2details
#18ACCEPTED0.03 s2details
#19ACCEPTED0.04 s2details
#200.03 s2details
#210.01 s2details
#22ACCEPTED0.22 s2details
#230.21 s2details
#240.20 s2details
#25ACCEPTED0.21 s2details
#260.20 s2details
#270.19 s2details
#28ACCEPTED0.13 s2details
#290.15 s2details
#30ACCEPTED0.01 s2details
#310.02 s2details
#320.03 s2details
#330.02 s2details
#34ACCEPTED0.05 s2details
#35ACCEPTED0.20 s2details

Code

#include <bits/stdc++.h>
 
using namespace std;
 
//#define FILE_IO
 
typedef double LD;
typedef pair<LD, LD> pld;
typedef complex<LD> Point;
 
const LD PI = atan(1.0) * 4.0;
const LD eps = 1e-8;
 
int N;
vector<pld> angles;
vector<pld> points;
 
int gint()
{
    char ch = getchar();
    int smn = 1;
    while(ch < '0' || '9' < ch)
    {
        if(ch == '-')   smn = -1;
        ch = getchar();
    }
    int x = 0;
    while('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * smn;
}
 
LD det(pld A, pld B, pld C)
{
    return A.first * (B.second - C.second) + B.first * (C.second - A.second) + C.first * (A.second - B.second);
}
 
LD dist(pld A, pld B)
{
    LD d = (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
    d = sqrt(d);
    return d;
}
 
vector<pld> intersect(vector<pld> a, vector<pld> b)
{
    vector<pld> sol;
    for(auto x: a)
        for(auto y: b)
        {
            LD st = max(x.first, y.first);
            LD dr = min(x.second, y.second);
            if(dr - st < eps)    continue;
            sol.emplace_back(st, dr);
        }
    sort(begin(sol), end(sol));
    return sol;
}
 
LD getAngle(pld A, pld B, LD ang)
{
    LD d = dist(A, B);
    Point Bprim(A.first + d, A.second);
    Point BB(B.first, B.second);
    Point AA(A.first, A.second);
    Bprim = (Bprim - AA) * Point(polar(1.0, (double)ang)) + AA;
    return 1.0;
    Point rot = (Bprim - AA) / (BB - AA);
    return arg(rot);
}
 
void solve(pld A, pld B, pld C)
{
    vector<pld> good;
    auto d = det(A, B, C);
    if(fabs(d) <= eps)
    {
        if( fabs(dist(A, B) + dist(B, C) - dist(A, C)) > eps )  angles.clear();
        return;
    }
 
    LD ang1 = getAngle(A, B, PI / 2.0);
    LD ang2 = getAngle(B, C, 3.0 * PI / 2.0);
 
    LD st, dr;
    if(d < 0.0)   st = ang2, dr = ang1;
    else    st = ang1, dr = ang2;
 
    while(st < 0)   st += PI;
    while(dr < st)  dr += PI;
    while(st > PI)  st -= PI, dr -= PI;
    while(dr > PI)  dr -= PI;
 
    if(st <= dr)    good.emplace_back(st, dr);
    else    good.emplace_back(st, PI), good.emplace_back(0, dr);
 
    angles = intersect(angles, good);
}
 
void solve_test()
{
    N = gint();
    angles.clear();
    angles.emplace_back(0.0, PI);
 
    points.resize(N + 2);
    for(int i = 1; i <= N; i++)
        points[i].first = gint(), points[i].second = gint();
 
    for(int i = 1; i + 2 <= N; i++)
    {
        solve(points[i], points[i + 1], points[i + 2]);
        //if(angles.empty())  continue;
    }
 
    if(angles.empty())
        printf("NO\n");
    else
        printf("YES\n");
}
 
int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
 
    int T = gint();
    for(int t = 1; t <= T; t++)
        solve_test();
 
    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
NO
...
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:

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

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

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

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

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

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

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

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

user output
NO
NO
NO
NO
NO
...
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
NO
NO
NO
...
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
NO
...
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 (bogdan10bos)

2:49:52 452:44:58 452:42:08 452:39:55 02:39:17 02:38:15 02:37:00 02:35:45 02:24:49 452:22:31 452:20:08 452:18:36 45