UVA1398 Meteor

每颗流星经过框的时间用一个左开右开的开区间来表示，然后就是简单的求最大区间覆盖问题了。

其中求开区间的方法很巧妙，可以节省一些代码量。

#include <iostream>
#include <algorithm>
using namespace std;
#define db double
const int N = 600000 + 1;
int n , T , tot, num , ans ;
double w , h ;
struct node {
	double times;
	int flag;
	bool operator < ( const node & rhs ) {
		if ( rhs . times != times )
			return times < rhs . times;
		return flag < rhs . flag ;
	}
} Time [ N ] ;
void work ( db , db , db , db& , db& ) ;
int main () {
	scanf ( "%d" , & T ) ;
	while ( T -- ) {
		ans = num = tot = 0 ; 
		scanf ( "%lf %lf" , &w , & h ) ;
		scanf ( "%d" , & n ) ;
		w = w * 1.00000; h = h * 1.000000;
		for ( int i = 0 ; i < n ; i ++ ) {
			static double x , y , a , b ;
			scanf ( "%lf%lf%lf%lf" , & x , & y , & a , & b ) ;
			double l , r ;
			l = 0 , r = 10000000 ;
			work ( x , a , w , l , r ) ;
			work ( y , b , h , l , r ) ; 
			//因为初始化时有 l = 0 ，所以 l 一定大于等于 0 。
			//r可能 < 0 ，但是 r 小于 0 时 满足 r < l 无解 。
			//这也是在求不等式时不要求 l , r 均大于等于 0 的原因。
			if ( r <= l ) continue;
			Time [ tot ] . times = l ; Time [ tot ] . flag = 1 ;
			tot ++ ;
			Time [ tot ] . times = r ; Time [ tot ] . flag = 0 ;
			tot ++ ;
		}
		sort ( Time , Time + tot ) ;
		for ( int i = 0 ; i < tot; i ++ ) {
			if ( Time [ i ] . flag == 0 ) num -- ;
			else { num ++ ; ans = max ( ans , num ) ; }
		}
		printf ( "%d\n" , ans ) ; 
	}
}
//解不等式
void work ( db x , db y , db limit , db &a , db &b ) {
	if ( y == 0 ) {
		if ( 0 < x && x < limit ) ;
		else b = a - 1 ; //有 ) ( ，因此两个区间求交集时一定有 b < a 在主函数中直接判断即可
	}
	if ( y < 0 ) {//向左跑
		a = max ( a , ( double ) ( limit - x ) / y ) ;
		b = min ( b , ( double ) ( - x / y ) ) ;
	}
	if ( y > 0 ) {//向右跑
		a = max ( a , ( double ) ( - x / y ) ) ;
		b = min ( b , ( double ) ( limit - x ) / y ) ;
	}
}