## 【POJ – 1066】Treasure Hunt【线段相交】

【POJ – 1066】Treasure Hunt【线段相交】

Solution:

```#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
double x, y;
Point operator - (const Point p) const {
Point ret = {x - p.x, y - p.y};
return ret;
}
double operator ^ (const Point p) const {
return x * p.y - y * p.x;
}
};
struct Seg {
Point s, e;
};

const int LIM = 35;
Seg data[LIM];

bool atTwoSide(const Seg s, const Point a, const Point b) {
Point v1 = s.e - s.s;
Point v2 = a - s.s;
Point v3 = b - s.s;
return (v1 ^ v2) * (v1 ^ v3) < 0;
}

double maxi(double a, double b) {return a > b ? a : b;}
double mini(double a, double b) {return a < b ? a : b;}

bool onSegment(const Seg &s, const Point &a) {
Point v1 = s.e - s.s;
Point v2 = a - s.s;
return v1 ^ v2 == 0;
}

int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lf%lf%lf%lf", &data[i].s.x, &data[i].s.y, &data[i].e.x, &data[i].e.y);
}
Point dest;
scanf("%lf%lf", &dest.x, &dest.y);
if (n == 0) {
printf("Number of doors = 1\n");
return 0;
}
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
Point tmp = data[i].s;
int tmpcnt = 0;
for (int j = 0; j < n; j++) {
if (!onSegment(data[j], tmp) && atTwoSide(data[j], tmp, dest))
tmpcnt++;
if (tmpcnt > ans) break;
}
if (tmpcnt < ans) ans = tmpcnt;
tmp = data[i].e;
tmpcnt = 0;
for (int j = 0; j < n; j++) {
if (!onSegment(data[j], tmp) && atTwoSide(data[j], tmp, dest))
tmpcnt++;
if (tmpcnt > ans) break;
}
if (tmpcnt < ans) ans = tmpcnt;
}
printf("Number of doors = %d\n", ans + 1);
return 0;
}
```