本文共 2115 字，大约阅读时间需要 7 分钟。
枚举边上相邻点的中点，和终点连线，计算其和其他线段的交点。
值得回味的地方是kuailezhish帮我想出的排序的方案。
#include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a))#define MAX(a,b) ((a)>(b)?(a):(b))#define MIN(a,b) ((a)<(b)?(a):(b))#define INF 0x3f3f3f3fusing namespace std;struct point { double x, y; void setPoint(double xx, double yy) { x = xx; y = yy; }};struct line { point s, e;};int n;line num[109];point ed, a[509];int acnt;double eps = 1e-8;int getval(point a) { int ret = 0; if(a.x <= eps) { ret = a.y; } else if(fabs(a.x - 100) <= eps) { ret = 101 + a.y; } else if(a.y <= eps) { ret = 202 + a.x; } else { ret = 303 + a.x; } return ret;}bool cmp1(point a, point b) { int ta = getval(a); int tb = getval(b); return ta < tb;}bool dy(double a, double b) { return fabs(a - b) < eps;}double mp(point a, point b, point c) { return ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y));}int iscross(line a, line b) { if(mp(a.s, a.e, b.s) * mp(a.s, a.e, b.e) < -eps && mp(b.s, b.e, a.s) * mp(b.s, b.e, a.e) < -eps) { return 1; } return 0;}int cntline(line t) { int ret = 1; for(int i = 0; i < n; i++) { ret += iscross(t, num[i]); } return ret;}int main() {#ifndef ONLINE_JUDGE freopen("F:/ACMData.txt","r",stdin);#endif scanf("%d", &n); acnt = 0; for(int i = 0; i < n; i++) { scanf("%lf%lf%lf%lf", &num[i].s.x, &num[i].s.y, &num[i].e.x, &num[i].e.y); a[acnt++] = num[i].s; a[acnt++] = num[i].e; } scanf("%lf%lf", &ed.x, &ed.y); a[acnt++].setPoint(0, 0); a[acnt++].setPoint(0, 100); a[acnt++].setPoint(100, 0); a[acnt++].setPoint(100, 100); sort(a, a + acnt, cmp1); int ret = INF; for(int i = 0; i < acnt - 1; i++) { if(dy(a[i].x, a[i + 1].x) && dy(a[i].y, a[i + 1].y)) { continue; } if(dy(a[i].x, a[i + 1].x) || dy(a[i].y, a[i + 1].y)) { line p; p.s = ed; p.e.setPoint(a[i].x / 2 + a[i + 1].x / 2, a[i].y / 2 + a[i + 1].y / 2); int tmp = cntline(p); ret = MIN(ret, tmp); } } printf("Number of doors = %d\n", ret); return 0;}
转载于:https://www.cnblogs.com/soenlit/p/3204307.html