很好的一道題。題意是，一個正方形圍牆內有一些交錯的內牆，內牆的端點都在正方形上，在正方形內部有一個點，求從正方形外到這個點的最少要走的門數，門只能是線段的中點。
思路很巧妙，因為從一個點到終點不可能“繞過”圍牆，只能傳過去，所以門是否開在中點是無所謂的，只要求四周線段中點到終點的線段與牆的最少交點個數即可。更進一步，實際上，只需判斷四周圍牆的所有點與終點的連線與內牆的最少交點加一即可。
請看下圖的紅色線，與藍色線交點，即是上述的交點。
#include <iostream>
#include <math.h>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define pi acos(-1.0)
struct point
{
double x, y;
};
struct line
{
point a, b;
};
//計算cross product (P1-P0)x(P2-P0)
double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}
//計算dot product (P1-P0).(P2-P0)
double dmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.x - p0.x) + (p1.y - p0.y)*(p2.y - p0.y);
}
//兩點距離
double distance(point p1, point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
//判三點共線
bool dots_inline(point p1, point p2, point p3)
{
return zero(xmult(p1, p2, p3));
}
//判點是否在線段上,包括端點
bool dot_online_in(point p, line l)
{
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
}
//判點是否在線段上,不包括端點
bool dot_online_ex(point p, line l)
{
return dot_online_in(p, l) && (!zero(p.x - l.a.x) || !zero(p.y - l.a.y)) && (!zero(p.x - l.b.x) || !zero(p.y - l.b.y));
}
//判兩點在線段同側,點在線段上返回0
bool same_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}
//判兩點在線段異側,點在線段上返回0
bool opposite_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
}
//判兩線段相交,包括端點和部分重合
bool intersect_in(line u, line v)
{
if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
}
//判兩線段相交,不包括端點和部分重合
bool intersect_ex(line u, line v)
{
return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
}
int main()
{
point p[100];
line wall[35], link[100];
int n;
while (std::cin >> n)
{
int j = 0;
for (int i = 0; i < n << 1; i++)//邊界點
{
std::cin >> p[i].x >> p[i].y;
}
for (int i = 0; i < n << 1; i++)//構造牆
{
wall[j].a = p[i];
wall[j++].b = p[++i];
}
double x, y;
std::cin >> x >> y;
int k = 0;
for (int i = 0; i < n << 1; i++)//構造寶藏點到邊界所有點的連線
{
link[k].a = p[i];
link[k].b.x = x, link[k++].b.y = y;
}
//for (int i = 0; i < n; i++)
//{
// std::cout << wall[i].a.x << ' ' << wall[i].a.y << ' ' << wall[i].b.x << ' ' << wall[i].b.y << std::endl;
//}
//for (int i = 0; i < n << 1; i++)
//{
// std::cout << link[i].a.x << ' ' << link[i].a.y << ' ' << link[i].b.x << ' ' << link[i].b.y << std::endl;
//}
int min = 100000;
for (int i = 0; i < n << 1; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (intersect_ex(link[i], wall[j]))
{
count++;
/*std::cout << link[i].a.x << '%' << link[i].a.y << '%' << link[i].b.x << '%' << link[i].b.y << std::endl;
std::cout << wall[j].a.x << '%' << wall[j].a.y << '%' << wall[j].b.x << '%' << wall[j].b.y << std::endl << std::endl;*/
}
}
//std::cout << count << std::endl;
if (count < min) min = count;
}
if (n == 0) std::cout << "Number of doors = 1" << std::endl;
else std::cout <<"Number of doors = "<< min + 1<< std::endl;
}
}
#include <iostream>
#include <math.h>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define pi acos(-1.0)
struct point
{
double x, y;
};
struct line
{
point a, b;
};
//計算cross product (P1-P0)x(P2-P0)
double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}
//計算dot product (P1-P0).(P2-P0)
double dmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.x - p0.x) + (p1.y - p0.y)*(p2.y - p0.y);
}
//兩點距離
double distance(point p1, point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
//判三點共線
bool dots_inline(point p1, point p2, point p3)
{
return zero(xmult(p1, p2, p3));
}
//判點是否在線段上,包括端點
bool dot_online_in(point p, line l)
{
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
}
//判點是否在線段上,不包括端點
bool dot_online_ex(point p, line l)
{
return dot_online_in(p, l) && (!zero(p.x - l.a.x) || !zero(p.y - l.a.y)) && (!zero(p.x - l.b.x) || !zero(p.y - l.b.y));
}
//判兩點在線段同側,點在線段上返回0
bool same_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}
//判兩點在線段異側,點在線段上返回0
bool opposite_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
}
//判兩線段相交,包括端點和部分重合
bool intersect_in(line u, line v)
{
if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
}
//判兩線段相交,不包括端點和部分重合
bool intersect_ex(line u, line v)
{
return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
}
int main()
{
point p[100];
line wall[35], link[100];
int n;
while (std::cin >> n)
{
int j = 0;
for (int i = 0; i < n << 1; i++)//邊界點
{
std::cin >> p[i].x >> p[i].y;
}
for (int i = 0; i < n << 1; i++)//構造牆
{
wall[j].a = p[i];
wall[j++].b = p[++i];
}
double x, y;
std::cin >> x >> y;
int k = 0;
for (int i = 0; i < n << 1; i++)//構造寶藏點到邊界所有點的連線
{
link[k].a = p[i];
link[k].b.x = x, link[k++].b.y = y;
}
//for (int i = 0; i < n; i++)
//{
// std::cout << wall[i].a.x << ' ' << wall[i].a.y << ' ' << wall[i].b.x << ' ' << wall[i].b.y << std::endl;
//}
//for (int i = 0; i < n << 1; i++)
//{
// std::cout << link[i].a.x << ' ' << link[i].a.y << ' ' << link[i].b.x << ' ' << link[i].b.y << std::endl;
//}
int min = 100000;
for (int i = 0; i < n << 1; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (intersect_ex(link[i], wall[j]))
{
count++;
/*std::cout << link[i].a.x << '%' << link[i].a.y << '%' << link[i].b.x << '%' << link[i].b.y << std::endl;
std::cout << wall[j].a.x << '%' << wall[j].a.y << '%' << wall[j].b.x << '%' << wall[j].b.y << std::endl << std::endl;*/
}
}
//std::cout << count << std::endl;
if (count < min) min = count;
}
if (n == 0) std::cout << "Number of doors = 1" << std::endl;
else std::cout <<"Number of doors = "<< min + 1<< std::endl;
}
}
