Submission #649573

#	Time	Username	Problem	Language	Result	Execution time	Memory
649573		ShirleyM	Printed Circuit Board (CEOI12_circuit)	C++17	0 / 100	38 ms	6092 KiB

circuit

#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;
}

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

Compilation message (stderr)

circuit.cpp: In function 'bool intersection(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
circuit.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

• Subtask 1: 0 / 100