Submission #116075

#	Time	Username	Problem	Language	Result	Execution time	Memory
116075		evpipis	Printed Circuit Board (CEOI12_circuit)	C++17	0 / 100	1085 ms	4600 KiB

circuit

#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 (stderr)

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