글 읽기 - 16491번: 대피소 찾기 반례

skyblue02 5년 전 0

맞는 것 같은데 반례를 못 찾겠습니다.

뭐가 문제일까요?

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int, int> pii;
pii robot[12],place[12];
int ans[12],chk[12],flag;
int n;
int ccw(pii O, pii A, pii B){
    return (A.Y-O.Y)*(B.X-O.X)-(B.Y-O.Y)*(A.X-O.X);
}
int ismeet(pii A, pii B, pii C, pii D){
    int a=ccw(A,B,C),b=ccw(A,B,D),c=ccw(C,D,A),d=ccw(C,D,B);
    if(a*b ==0 && c*d == 0){
        if(b < a) swap(a, b);
        if(d < c) swap(c, d);
        return b>= c && d >=a;
    }
    return a*b<=0 && c*d<=0;
}
int ava(){
    int i,j;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            if(ismeet(robot[i],place[ans[i]],robot[j],place[ans[j]])) return 0;
        }
    }
    return 1;
}
void f(int lv){
    int i;
    if(lv>n){
        if(ava()){
            for(i=1;i<=n;i++){
                printf("%d\n",ans[i]);
            }
            flag=1;
            return;
        }
        return;
    }
    for(i=1;i<=n;i++)if(!chk[i]){
        chk[i]=1;
        ans[lv]=i;
        f(lv+1);
        if(flag) return;
        chk[i]=0;
    }
    return;
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d %d",&robot[i].X,&robot[i].Y);
    for(i=1;i<=n;i++) scanf("%d %d",&place[i].X,&place[i].Y);
    f(1);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16491번: 대피소 찾기 반례

skyblue02 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말