oj.uz

Submission #116075

# Submission time Handle Problem Language Result Execution time Memory
116075 2019-06-10T11:21:35 Z evpipis Printed Circuit Board (CEOI12_circuit) C++17
0 / 100
 100 ms 4600 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 2e5+5;
ii po[len];
vector<int> out;

ll ccw(ii a, ii b, ii c){
    return (b.fi-a.fi)*1LL*(c.se-a.se) - (b.se-a.se)*1LL*(c.fi-a.se);
}

double dis(ii a, ii b){
    return sqrt((a.fi-b.fi)*1LL*(a.fi-b.fi) + (a.se-b.se)*1LL*(a.se-b.se));
}

bool bel(ii a, ii b, ii c){
    return (dis(a, b) == dis(a, c)+dis(c, b));
}

bool inter(ii a, ii b, ii x, ii y){
    if (bel(a, b, x) || bel(a, b, y) || bel(x, y, a) || bel(x, y, b))
        return true;

    int cx = ccw(a, b, x), cy = ccw(a, b, y), ca = ccw(x, y, a), cb = ccw(x, y, b);
    if (cx == 0 || cy == 0 || ca == 0 || cb == 0)
        return false;
    return ((cx/abs(cx))*(cy/abs(cy)) < 0 && (ca/abs(ca))*(cb/abs(cb)) < 0);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &po[i].fi, &po[i].se);
    po[n] = po[0];

    for (int i = 0; i < n; i++){
        int good = 1;
        for (int j = 0; j < n; j++){
            //printf("j = %d\n", j);
            if (i == j || i == (j+1)%n)
                continue;

            if (inter(mp(0, 0), po[i], po[j], po[j+1]))
                good = 0;
        }

        //printf("i = %d, good = %d\n", i, good);
        if (good)
            out.pb(i+1);
    }

    printf("%d\n", out.size());
    for (int i = 0; i < out.size(); i++)
        printf("%d ", out[i]);
    printf("\n");
    return 0;
}
/*
11
7 6
4 4
3 2
1 3
9 9
13 4
8 1
6 4
9 5
8 3
11 5

*/

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:60:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", out.size());
                    ~~~~~~~~~~^
circuit.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < out.size(); i++)
                     ~~^~~~~~~~~~~~
circuit.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
circuit.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &po[i].fi, &po[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Incorrect 47 ms 376 KB Output isn't correct
3 Execution timed out 391 ms 400 KB Time limit exceeded
4 Execution timed out 685 ms 688 KB Time limit exceeded
5 Execution timed out 1066 ms 512 KB Time limit exceeded
6 Execution timed out 1066 ms 512 KB Time limit exceeded
7 Execution timed out 1075 ms 768 KB Time limit exceeded
8 Execution timed out 1085 ms 512 KB Time limit exceeded
9 Execution timed out 1076 ms 512 KB Time limit exceeded
10 Execution timed out 1062 ms 512 KB Time limit exceeded
11 Execution timed out 1085 ms 512 KB Time limit exceeded
12 Execution timed out 1070 ms 640 KB Time limit exceeded
13 Execution timed out 1074 ms 896 KB Time limit exceeded
14 Execution timed out 1071 ms 1024 KB Time limit exceeded
15 Execution timed out 1069 ms 1408 KB Time limit exceeded
16 Execution timed out 1072 ms 2296 KB Time limit exceeded
17 Execution timed out 1072 ms 2428 KB Time limit exceeded
18 Execution timed out 1072 ms 4344 KB Time limit exceeded
19 Execution timed out 1076 ms 4344 KB Time limit exceeded
20 Execution timed out 1080 ms 4600 KB Time limit exceeded