oj.uz

Submission #649575

# Submission time Handle Problem Language Result Execution time Memory
649575 2022-10-10T16:28:36 Z ShirleyM Printed Circuit Board (CEOI12_circuit) C++17
10 / 100
 100 ms 3540 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1; i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()
#define fast {ios_base::sync_with_stdio(0); cin.tie(0);}

const int inf = 1e18;
const int INF = 1e9;

int n;

int mult(int x1, int y1, int x2, int y2, int x3, int y3){
    x2-=x1; x3-=x1;
    y2-=y1; y3-=y1;
    int ans = (x2*y3 - x3*y2);
    return ans;
}

int dir(int x1, int y1, int x2, int y2, int x3, int y3){
    int prod = mult(x1,y1,x2,y2,x3,y3);
    if(prod>0) return 1;
    else if(prod<0) return -1;
    return 0;
}

bool on_line(int x1, int y1, int x2, int y2, int x3, int y3){
    bool ans = (min(x1,x2)<=x3 && x3<=max(x1,x2) && min(y1,y2) <= y3 && y3<=max(y1,y2));
    return ans;
}


bool intersection(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
    int d1 = dir(x1,y1,x2,y2,x4,y4);
    int d2 = dir(x1,y1,x2,y2,x3,y3);
    int d3 = dir(x4,y4,x3,y3,x2,y2);
    int d4 = dir(x4,y4,x3,y3,x1,y1);
    if(d1*d2<0 && d3*d4<0) return 1;
    if(!d1 && on_line(x1,y1,x2,y2,x4,y4)) return 1;
    if(!d2 && on_line(x1,y1,x2,y2,x3,y3)) return 1;
    if(!d3 && on_line(x3,y3,x4,y4,x2,y2)) return 1;
    if(!d4 && on_line(x3,y3,x4,y4,x1,y1)) return 1;
    return 0;
}

int32_t main()
{
    fast;
    cin >> n;
    vii p(n); loop(i,0,n) cin >> p[i].x >> p[i].y;
    vi good;
    loop(i,0,n){
        bool ok=1;
        int x1=0, y1=0, x2 = p[i].x, y2 = p[i].y;
        loop(j,0,n){
            int next = (j+1)%n;
            int x3 = p[j].x, y3 = p[j].y;
            int x4 = p[next].x, y4 = p[next].y;
            if(next != i && j != i){
                if(!(on_line(x3,y3,x4,y4,x2,y2)&&!dir(x3,y3,x2,y2,x4,y4)) && intersection(x1,y1,x2,y2,x3,y3,x4,y4)){
                    ok=0; break;
                }
            }
            else{
                if(!dir(x3,y3,x4,y4,x1,y1) && on_line(x1,y1,x2,y2,x3,y3) && on_line(x1,y1,x2,y2,x4,y4)){
                    ok=0; break;
                }
            }
        }
        if(ok) good.pb(i+1);
    }
    sort(all(good));
    cout << good.size() << endl;
    for(int ind:good) cout << ind << " ";
    return 0;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Execution timed out 115 ms 416 KB Time limit exceeded
4 Execution timed out 249 ms 412 KB Time limit exceeded
5 Execution timed out 645 ms 596 KB Time limit exceeded
6 Execution timed out 641 ms 604 KB Time limit exceeded
7 Execution timed out 1078 ms 724 KB Time limit exceeded
8 Execution timed out 426 ms 532 KB Time limit exceeded
9 Execution timed out 698 ms 684 KB Time limit exceeded
10 Execution timed out 665 ms 600 KB Time limit exceeded
11 Execution timed out 784 ms 616 KB Time limit exceeded
12 Execution timed out 1083 ms 724 KB Time limit exceeded
13 Execution timed out 1086 ms 852 KB Time limit exceeded
14 Execution timed out 451 ms 1068 KB Time limit exceeded
15 Execution timed out 1069 ms 1236 KB Time limit exceeded
16 Execution timed out 1075 ms 2004 KB Time limit exceeded
17 Execution timed out 1084 ms 2004 KB Time limit exceeded
18 Execution timed out 1085 ms 3540 KB Time limit exceeded
19 Execution timed out 1089 ms 3540 KB Time limit exceeded
20 Execution timed out 1079 ms 3512 KB Time limit exceeded