글 읽기 - 반례나 틀린부분이 있을까요?

onseokjun 2년 전 0

convex hull 사용 안하고 그냥 모든 변에 대해서 다른 점들과의 거리의 최댓값을 구하고 그중 최솟값을 구했습니다 어짜피 볼록껍질 내부에 점은 후보에 안들어간다고 생각하고 convex hull은 시간을 줄이고 효율적이게 해주는게 아닌가 해서요

그런데 시간 초과가 아니라 틀렸다고 나옵니다 출력에서 잘못된건지 아니면 볼록껍질로만 해야하는 이유가 있는지 볼록껍질 내부에 점이 변과 가장 먼 점의 후보가 될수 있는지 그렇다면 반례가 궁금합니다

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <random>
#include <queue>

using namespace std;

struct point{
    double x;
    double y;
};


double distpoint(point a, point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double distance(point a, point b, point c){
    double area = (a.x * b.y) + (b.x * c.y) + (c.x * a.y) - (a.y * b.x) - (b.y * c.x) - (a.x * c.y);

    return fabs(area) / distpoint(b, c);
}


int main() {
    int test = 1;
    while(1){
        int N;
        cin >> N;

        if(N == 0){
            break;
        }

        vector <point> list(2 * N);
        for(int i = 0; i < N; i++){
            double a, b;
            cin >> a >> b;
            list[i].x = a;
            list[i].y = b;
            list[i + N].x = a;
            list[i + N].y = b;
        }

        double min = 100000;
        for(int i = 0; i < N; i++){
            double max = 0;
            for(int j = i + 2; j < i + N; j++){
                double temp = distance(list[j], list[i], list[i + 1]);
                if(temp == 0){
                    continue;
                }
                if(temp > max){
                    max = temp;
                }
            }
            if(max < min){
                min = max;
            }
        }
        cout.setf(ios::fixed, ios::floatfield);
        cout.precision(2);
        cout << "Case " << test << ": " << ceil(min * 100) / 100 << "\n";
        test ++;
    }
	return 0;
}

byeongkeunahn 2년 전 1

풀이는 다음 가정 (*)에 의존합니다.

(*) 한 변 AB와 다른 점 C을 잡았을 때 C를 지나고 AB에 평행한 직선을 L이라 한다면 다른 모든 점이 직선 AB와 직선 L 사이에 들어온다는 것을 보장할 수 있다.

하지만 Convex hull이 아니라면 (*)를 보장할 수 없습니다. 피자를 팔각형으로 볼 때 한 조각만 먹고 남은 모양을 생각해 보시면 좋을 것 같아요.

도형을 통과시킬 수 있는 것과 도형의 Convex hull을 통과시킬 수 있는 것은 서로 동치인데, Convex hull로 바라봤을 때에만 (*)이 성립하기 때문에 Convex hull로 풀어야 한다고 이해하시면 될 듯합니다.

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

문제

문제

출처

ICPC

반례나 틀린부분이 있을까요?

onseokjun 2년 전 0

byeongkeunahn 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말