1 #include <iostream> 2 #include <string.h> 3 #include <string> 4 #include <fstream> 5 #include <algorithm> 6 #include <stdio.h> 7 #include <vector> 8 #include <queue> 9 using namespace std; 10 const double eps = 1e-8; 11 #define MAXN 5005 12 struct Target{ 13 long double y,l,r; 14 Target(long double _y = 0.0, long double _l = 0.0, long double _r = 0.0) { 15 y = _y, l = _l, r = _r; 16 if (l > r) swap(l, r); 17 } 18 }; 19 vector<Target> rec; 20 bool cmp(Target a, Target b) { 21 return a.y < b.y; 22 } 23 24 int test(long double x) { 25 long double L = (rec[0].l - x - eps) / rec[0].y, R = (rec[0].r - x + eps) / rec[0].y; 26 for(int i=1;i<=(rec.size()- 1);i++) { 27 long double tmpL = (rec[i].l - x - eps) / rec[i].y, tmpR = (rec[i].r - x + eps) / rec[i].y; 28 if (R < tmpL) return 1; 29 if (tmpR < L) return -1; 30 L = max(tmpL, L), R = min(tmpR, R); 31 } 32 return 0; 33 } 34 35 bool bs(long double w) 36 { 37 long double l=0, r = w, m; 38 while (r - l > eps) { 39 m = (l + r) / 2.0; 40 int res = test(m); 41 if (res == 0) { 42 // cout << m << endl; 43 return true; 44 } else if (res == -1) l = m; 45 else r = m; 46 } 47 return false; 48 } 49 int main() 50 { 51 int W,T,n; 52 scanf("%d",&T); 53 while(T--) 54 { 55 scanf("%d",&W); 56 scanf("%d",&n); 57 long double D,L,R; 58 rec.clear(); 59 for(int i=0;i<n;i++) 60 { 61 cin>>D>>L>>R; 62 rec.push_back(Target(D,L,R)); 63 } 64 sort(rec.begin(),rec.end(),cmp); 65 bs(W) ? puts("YES") : puts("NO"); 66 } 67 68 69 return 0; 70 }
http://www.cnblogs.com/LyonLys/archive/2013/03/04/LA_4253_Lyon.html
抄袭了下~~ 二分+枚举
有空重写=。=