oj.uz

답안 #649573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649573 2022-10-10T16:28:01 Z ShirleyM Printed Circuit Board (CEOI12_circuit) C++17
0 / 100
 38 ms 6092 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;
}

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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 3 ms 624 KB Output isn't correct
6 Incorrect 3 ms 588 KB Output isn't correct
7 Incorrect 4 ms 840 KB Output isn't correct
8 Incorrect 2 ms 468 KB Output isn't correct
9 Incorrect 2 ms 460 KB Output isn't correct
10 Incorrect 3 ms 596 KB Output isn't correct
11 Incorrect 3 ms 580 KB Output isn't correct
12 Incorrect 5 ms 856 KB Output isn't correct
13 Incorrect 7 ms 1108 KB Output isn't correct
14 Incorrect 8 ms 1364 KB Output isn't correct
15 Incorrect 10 ms 1748 KB Output isn't correct
16 Incorrect 17 ms 3040 KB Output isn't correct
17 Incorrect 18 ms 3160 KB Output isn't correct
18 Incorrect 38 ms 5856 KB Output isn't correct
19 Incorrect 36 ms 5864 KB Output isn't correct
20 Incorrect 34 ms 6092 KB Output isn't correct