算法题：uva 1398 - Meteor

算法题：uva 1398 - Meteor2014-03-17 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4144

先存代码，睡觉去了睡觉

代码：

#include<iostream>#include<cstdio>#include<algorithm>#include<cctype>using namespace std;const int LCM = 2520;const int MAXN = 100010;int w, h, n, idx;inline bool getTime（int x, int y, int& a, int& b）{int tx1, tx2, ty1, ty2;if（a）{tx1 = （w-x）*LCM/a, tx2 = （-x）*LCM/a;if（tx1<0 && tx2<0） return false;} else{if（x>=w || x<=0） return false;tx1 = 0,tx2 = 1e9;}if（b）{ty1 = （h-y）*LCM/b, ty2 = （-y）*LCM/b;if（ty1<0 && ty2<0） return false;} else{if（y>=h || y<=0） return false;ty1 = 0, ty2 = 1e9;}if（tx1 > tx2） swap（tx1, tx2）;if（ty1 > ty2） swap（ty1, ty2）;if（tx1<0） tx1=0;if（ty1<0） ty1=0;a = max（tx1, ty1）;b = min（tx2, ty2）;return a<b;}struct Node{int pos;int type;bool operator<（const Node&rhs）const{if（pos ！= rhs.pos） return pos<rhs.pos;return type<rhs.type;}}arr[MAXN*2];int main（）{ int nCase;scanf（"%d", &nCase）;while（nCase--）{int x,y,a,b;scanf（"%d%d%d",&w,&h,&n）;idx = 0;for（int i=0; i<n; ++i）{scanf（"%d%d%d%d",&x,&y,&a,&b）;if（getTime（x, y, a, b））{arr[idx].pos = a; arr[idx++].type = 1;arr[idx].pos = b;arr[idx++].type = -1;}}sort（arr, arr+idx）;int cur=0, maxx=0;for（int i=0; i<idx; ++i）{if（arr[i].type>0） maxx = max（++cur, maxx）;else --cur;}printf（"%d
", maxx）;}return 0;}