CSES - Datatähti Open 2019

CSES - Datatähti Open 2019 - Results

Submission details
Task:	Function
Sender:	bogdan10bos
Submission time:	2019-01-20 14:09:45 +0200
Language:	C++
Status:	READY
Result:	45

Feedback
group	verdict	score
#1	ACCEPTED	45
#2	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.03 s	1	details
#2	ACCEPTED	0.03 s	1	details
#3	ACCEPTED	0.01 s	1	details
#4	ACCEPTED	0.02 s	1	details
#5	ACCEPTED	0.16 s	1	details
#6	ACCEPTED	0.05 s	1	details
#7	ACCEPTED	0.04 s	1	details
#8	ACCEPTED	0.05 s	1	details
#9	ACCEPTED	0.03 s	1	details
#10	WRONG ANSWER	0.03 s	2	details
#11	ACCEPTED	0.01 s	2	details
#12	ACCEPTED	0.01 s	2	details
#13	ACCEPTED	0.01 s	2	details
#14	ACCEPTED	0.16 s	2	details
#15	ACCEPTED	0.15 s	2	details
#16	ACCEPTED	0.16 s	2	details
#17	ACCEPTED	0.16 s	2	details
#18	ACCEPTED	0.12 s	2	details
#19	ACCEPTED	0.12 s	2	details
#20	ACCEPTED	0.12 s	2	details
#21	WRONG ANSWER	0.01 s	2	details
#22	TIME LIMIT EXCEEDED	--	2	details
#23	TIME LIMIT EXCEEDED	--	2	details
#24	TIME LIMIT EXCEEDED	--	2	details
#25	TIME LIMIT EXCEEDED	--	2	details
#26	TIME LIMIT EXCEEDED	--	2	details
#27	TIME LIMIT EXCEEDED	--	2	details
#28	TIME LIMIT EXCEEDED	--	2	details
#29	TIME LIMIT EXCEEDED	--	2	details
#30	ACCEPTED	0.01 s	2	details
#31	ACCEPTED	0.02 s	2	details
#32	ACCEPTED	0.01 s	2	details
#33	ACCEPTED	0.03 s	2	details
#34	ACCEPTED	0.16 s	2	details
#35	TIME LIMIT EXCEEDED	--	2	details

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-9;

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;
    Point rot = (Bprim - AA) / (BB - AA);
    LD ans = atan2(rot.imag(), rot.real());
    return ans;
}

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: ACCEPTED

input
`12 2 0 0 1 1 5 ...` view save

correct output
`YES YES NO YES YES ...` view save

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

input
`100 4 87 81 -84 42 18 -46 ...` view save

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

user output
`YES YES YES YES YES ...` 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: ACCEPTED

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: ACCEPTED

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: ACCEPTED

input
`100 45 -100 89 -100 90 -97 90 ...` view save

correct output
`YES NO NO NO NO ...` view save

user output
`YES NO NO NO NO ...` Truncated

Test 10

Group: 2

Verdict: WRONG ANSWER

input
`13 2 0 0 1 1 5 ...` view save

correct output
`YES YES NO YES YES ...` view save

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

input
`100 4 891187584 -889373775 -453505448 -469134344 -683807769 8725517 ...` view save

correct output
`YES NO YES NO NO ...` view save

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

input
`100 1000 -911073332 -1000000000 -905159999 -1000000000 -904949593 -999999999 ...` view save

correct output
`YES YES YES NO NO ...` view save

user output
`YES YES YES NO NO ...` Truncated

Test 16

Group: 2

Verdict: ACCEPTED

input
`100 1000 -1000000000 950042028 -946551105 -1000000000 -940508390 -1000000000 ...` view save

correct output
`NO YES YES YES NO ...` view save

user output
`NO YES YES YES NO ...` Truncated

Test 17

Group: 2

Verdict: ACCEPTED

input
`100 1000 -949977239 -1000000000 -948279892 -1000000000 -947497811 -999999999 ...` view save

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

user output
`YES YES YES YES YES ...` 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: ACCEPTED

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: WRONG ANSWER

input
`13 2 0 0 1 1 5 ...` view save

correct output
`YES YES NO YES YES ...` view save

user output
`YES YES NO YES NO ...` view save

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 999748 -995394098 -1000000000 -995392159 -1000000000 -995386584 -999999999 ...` view save

correct output
`NO` view save

user output
(empty)

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 1000000 -954368893 -1000000000 -954366895 -1000000000 -954364896 -999999999 ...` view save

correct output
`YES` view save

user output
(empty)

Test 24

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 1000000 -1000000000 928772368 -1000000000 928772506 -999999999 928772642 ...` view save

correct output
`YES` view save

user output
(empty)

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1 999754 -901705699 -1000000000 -901702695 -1000000000 -901702062 -999999999 ...` view save

correct output
`NO` view save

user output
(empty)

Test 26

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`100 10000 -1000000000 919783772 -918885599 -1000000000 -918825263 -1000000000 ...` view save

correct output
`NO YES YES NO NO ...` view save

user output
(empty)

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`10 99998 -997024120 -77018772 -997011201 -77017738 -996986132 -77015834 ...` view save

correct output
`YES YES NO YES YES ...` view save

user output
(empty)

Test 28

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`100 7934 -10000 9905 -10000 9906 -9999 9906 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
(empty)

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`100 9710 -99754 -6983 -99786 -6055 -99751 -6548 ...` view save

correct output
`YES NO NO NO NO ...` view save

user output
(empty)

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: ACCEPTED

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

Test 33

Group: 2

Verdict: ACCEPTED

input
`100 5 -124483012 623794901 233757283 -234519096 -987338502 737259422 ...` view save

correct output
`NO NO YES NO NO ...` view save

user output
`NO NO YES 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: TIME LIMIT EXCEEDED

input
`100 10000 642800667 -694556052 -343795089 -341227394 800920828 676674460 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
(empty)

Datatähti Open 2019

Function

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Tasks

Submissions (bogdan10bos)