계산 기하학:선분 교차(미궁 보물 찾기)

계산 기하학:선분 교차(미로 보물 찾기)시간 제한(Common/Java):1000 MS/3000 MS         Memory Limit:65536KByte Description          ACM 이라는 보물 찾 는 사람 이 보물 지 도 를 찾 았 습 니 다.보물 지도 에 따라 미 로 를 찾 았 습 니 다.이것 은 아주 특별한 미로 입 니 다.미 로 는 100*100 의 정사각형 구역 이 고 그 안에 많은 벽 이 있 습 니 다.이 벽 들 은 모두 직선 으로 구성 되 어 있 습 니 다.다음 과 같 습 니 다.    벽 은 미 로 를 많은 보물 실 로 나 누 었 고 그 어떠한 보물 실 사이 에 도 문 이 없 었 다.      ACM 은 현재 굴착 장비 로 인접 한 두 보물 실의 벽 사이 에 문 하 나 를 뚫 고 미궁 속 보물 을 꺼 낼 준 비 를 하고 있다.     하지만 문 을 파 는 것 은 시간 이 많이 걸 리 는 일이 다.ACM 은 가능 한 한 적은 문 을 열 어 보물 을 꺼 내 려 고 한다.지금 은 최소한 몇 개의 문 을 열 어야 하 는 지 판단 하 는 절 차 를 만들어 보 자.Input
   첫 번 째 줄 에 정수 N(N<10)을 입력 하면 테스트 데이터 그룹 수 를 표시 합 니 다.      각 그룹의 테스트 데이터 의 첫 줄 은 하나의 정수 n(0<=n<=30)으로 벽의 개 수 를 대표 한다.그 다음 n 줄 에는 네 개의 정수 x1,x2,y1,y2 가 있 는데 이 네 개의 수 는 각각 한 벽의 두 단점 을 대표 하 는 좌표 이다.외곽 의 정사각형 네 개의 정점 은(0,0)(0,100)(100,0)(100,100)이 네 개의 벽 이 위의 n 개 수 에 고정 되 어 있 지 않다.두 선의 교점 에서 문 을 열 어 서 는 안 된다 는 것 을 주의해 라.      데 이 터 는 임의의 두 중간 벽의 교점 이 사방 의 벽 에 있 지 않도록 보장 한다.      모든 벽 을 진 후 두 개의 수,x,y(정수 가 아 닐 수 있 음)를 입력 하여 보물 의 좌 표를 표시 합 니 다.Output      최소 굴착 이 필요 한 문의 개 수 를 출력 하 다.Sample Input 1 7  20 0 37 100  40 0 76 100  85 0 0 75  100 90 0 90  0 71 100 61  0 14 100 38  100 47 47 100  54.5 55.4  Sample Output 2 Hint  선분 교차,매 거 소스 poj 1066
문제 풀이:
모든 벽의 단점+보물 의 위 치 를 직접 매 거 하여 하나의 선분 으로 삼 아 그 와 교차 하 는 최소 선분 수 를 구한다.답 이다.
Poj 의 데이터 가 비교적 강하 다.
주의해 야 할 점:
1.벽의 수가 0 이 더 라 도 보물 의 위 치 를 알 아야 한다.
2.Poj 이 문 제 는 데 이 터 를 입력 하 는 것 이지 만 다 중 스 레 드 인 것 같 습 니 다.
3.교차 판단 은 0 보다 적 으 면 된다.
AC 코드:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 35;
const int INF = 0xffffff;
const double eps = 1e-8;

struct POINT{
    double x, y;
};

struct LINE{
    POINT a, b;
}l[N];
int n;

double cross(POINT o, POINT a, POINT b){
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

int Judge(POINT X, POINT Y){
    int ans = 0;
    for(int i = 0; i < n; i ++){
//        printf("cross = %.2lf
", cross(X, l[i].a, l[i].b) * cross(Y, l[i].a, l[i].b));
        if(cross(X, l[i].a, l[i].b) * cross(Y, l[i].a, l[i].b) < -eps)
        ans ++;
    }
//    printf("ans = %d
", ans);
    return ans;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        scanf("%d", &n);
        if(n == 0){
            puts("1");
            continue;
        }
        for(int i = 0; i < n; i ++){
            scanf("%lf %lf %lf %lf", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y);
        }
        POINT d;
        scanf("%lf %lf", &d.x, &d.y);
        int ans = INF;
        for(int i = 0; i < n; i++){
            ans = min(Judge(l[i].a, d), ans);
            ans = min(Judge(l[i].b, d), ans);
//            printf("ans = %d
", ans);
        }
        printf("%d
", ans + 1);
    }
    return 0;
}