글 읽기 - 14616 번 이분 탐색 방법에서 틀린 이유가 뭘까요 ?

kim8738 6년 전 0

특별히 문제 될 것이 없어보이는데요...

문제 될 부분이 있나요 ?

#include <stdio.h>
#include <memory.h>
#define MAX 100000

struct point {
    long long int x , y;
};
typedef struct point P;

struct line {
    P p1 , p2;
};
typedef struct line L;

P ps[MAX];
L ls[MAX];

bool cmp(P * p1 , P * p2) {
    return p1->y * p2->x < p2->y * p1->x;
}

void swap(P* p1 , P* p2) {
    P t;
    memcpy(&t, p1, sizeof(P));
    memcpy(p1 , p2 , sizeof(P));
    memcpy(p2 , &t , sizeof(P));
}

void qsort_m(P * arr , int left, int right) {
    int l = left;
    int r = right;
    P * p = &arr[(l+r)/2];
    
    while(l <= r) {
        while(cmp(&arr[l], p)) l++;
        while(cmp(p, &arr[r])) r--;
        
        if(l <= r) {
            swap(&arr[l] , &arr[r]);
            l++;
            r--;
        }
    }
    
    if(l < right) qsort_m(arr, l, right);
    if(left < r) qsort_m(arr, left, r);
}

bool bisearch(P* a , int l , int r, P *p1 , P* p2) {
    if(l > r) return false;
    
    int pi = (l+r)/2;
    P* p = &a[pi];
    if(cmp(p2 , p)) {
        return bisearch(a, l, pi -1, p1, p2);
    } else if(cmp(p , p1)) {
        return bisearch(a, pi + 1, r, p1, p2);
    } else {
        return true;
    }
    return false;
}

void process(int T) {
    int N , M;
    scanf("%d" , &N);
    for(int i = 0 ; i < N; i++) {
        scanf("%lld %lld %lld %lld", &ls[i].p1.x
              ,&ls[i].p1.y
              ,&ls[i].p2.x
              ,&ls[i].p2.y);
        if(cmp(&ls[i].p2 , &ls[i].p1))
            swap(&ls[i].p2 , &ls[i].p1);
    }
    
    scanf("%d" , &M);
    for(int i = 0 ; i < M; i++) {
        scanf("%lld %lld", &ps[i].x , &ps[i].y);
    }
    
    qsort_m(ps, 0, M - 1);
    
    int sum = N;
    for(int i = 0 ; i < N; i++) {
        if(bisearch(ps , 0 , M -1, &ls[i].p1 , &ls[i].p2)) {
            sum--;
        }
    }
    
    printf("%d\n" , sum);
}

int main() {
    process(0);
    return 1;
}

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

문제

문제

출처

ICPC

14616 번 이분 탐색 방법에서 틀린 이유가 뭘까요 ?

kim8738 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말