本文主要是介绍LA 3905 Meteor / 区间扫描，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求哪一时刻 框框里的点最多 每个点在做运动（在边框上不算）
求出每个点经过框框的区间 在2维坐标系以x表示 是开区间 因为区间边上不算
假设有一条竖线从左到右扫描过去 也就是求哪一时刻扫描线相交的区间最多
可以设cnt = 0每遇到左区间++右区间--求最大的cnt 然后一个区间右端点与一个区间的左区间相同 要先算右区间因为是开区间
书上的代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;const int maxn = 100010;
struct Event
{double x;int type;bool operator < (const Event& a) const{return x < a.x || (x == a.x && type > a.type);}
}event[maxn*2];void update(int x, int a, int w, double& l, double& r)
{if(a == 0){if(x <= 0 || x >= w)r = l - 1;}else if(a > 0)//0 < x+at < w <=> t > -x/a && t < (w-x)/a{l = max(l, -(double)x/a);r = min(r, (double)(w-x)/a);}else if(a < 0)//0 < x+at < w <=> t < -x/a && t > (w-x)/a{l = max(l, (double)(w-x)/a);r = min(r, -(double)x/a);}
}
int main()
{int T;scanf("%d", &T);while(T--){int w, h, n, e = 0;scanf("%d %d %d", &w, &h, &n);for(int i = 0; i < n; i++){int x, y, a, b;scanf("%d %d %d %d", &x, &y, &a, &b);double l = 0, r = 1e9;update(x, a, w, l, r);update(y, b, h, l, r);if(l < r){event[e++]= (Event){l, 0};event[e++]= (Event){r, 1};}}sort(event, event+e);int cnt = 0;int ans = 0;for(int i = 0; i < e; i++){if(event[i].type == 0)cnt++;elsecnt--;ans = max(ans, cnt);}printf("%d\n", ans);}return 0;
}
这篇关于LA 3905 Meteor / 区间扫描的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
