글 읽기 - 반례를 보여주실분 있으실까요?

onseokjun 2년 전 0

먼저 두 선분의 각각 끝점중 같은 점이 있다면 1

그렇지 않다면 ccw 이용해서 네 점이 일직선 위에 있을때 한 선분의 두 점이 다른 선분의 두 점보다 왼쪽이나 오른쪽에 있어서 만나지 않으면 0, 그렇지 않으면 1

두 경우 모두 아니라면 선분 교차 1처럼 ccw 의 곱이 0 이하면 1, 그 외의 경우는 0

주어진 데이터나 질문에 있는 데이터는 정답이 나와서 또 다른 반례가 주어져야 어떤 경우를 추가해줘야 할지 알수 있을것 같습니다

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct point{
    long long x;
    long long y;
}point;

int comp(point a, point b){
    if(a.x == b.x && a.y == b.y){
        return 1;
    }
    return 0;
}

int ccw(point A, point B, point C) {
    long long 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);
    if (area > 0){
        return 1;
    }
    else if (area < 0){
        return -1;
    }
    else {
        return 0;
    }
}

int main(){
    point points[5];
    for(int i = 0; i < 4; i++){
        scanf("%lld %lld", &points[i].x, &points[i].y);
    }

    int ans = 0;

    if(comp(points[0], points[2]) || comp(points[0], points[3]) || comp(points[1], points[2]) || comp(points[1], points[3])) {
        ans = 1;
    }   
    else if(ccw(points[0], points[1], points[2]) * ccw(points[0], points[1], points[3]) == 0 && ccw(points[2], points[3], points[0]) * ccw(points[2], points[3], points[1]) == 0){
        
        long long a, b, c, d;
        if(points[0].x < points[1].x){
            a = points[0].x; b = points[1].x;
        }
        else{
            b = points[0].x; a = points[1].x;
        }

        if(points[2].x < points[3].x){
            c = points[2].x; d = points[3].x;
        }
        else{
            d = points[2].x; c = points[3].x;
        }

        if(b < c || d < a){
            ans = 0;
        }
        else{
            ans = 1;
        }
    }
    else if(ccw(points[0], points[1], points[2]) * ccw(points[0], points[1], points[3]) <= 0 && ccw(points[2], points[3], points[0]) * ccw(points[2], points[3], points[1]) <= 0){
        ans = 1;
    }
    else{
        ans = 0;
    }

    printf("%d", ans);
    return 0;
}

onseokjun 2년 전 1

아 죄송합니다 애초에 질문 모두 해봤다고 생각했는데 x좌표가 모두 같은 경우를 생각을 안했네요

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

문제

문제

출처

ICPC

반례를 보여주실분 있으실까요?

onseokjun 2년 전 0

onseokjun 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말