Guest User

Lights

a guest
Aug 22nd, 2014
266
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. //Bismillahir Rahmanir Rahim
  2. /******Harun Or Rashid******/
  3. /***********Template Starts Here***********/
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cstring>
  7. #include<cmath>
  8. #include<cctype>
  9. #include<cstdlib>
  10. #include<string>
  11. #include<vector>
  12. #include<set>
  13. #include<stack>
  14. #include<queue>
  15. #include<map>
  16. #include<algorithm>
  17. using namespace std;
  18.  
  19. #define MEM(a,b) memset(a,b,sizeof(a))
  20. #define CLR(a) memset(a,0,sizeof(a))
  21. #define MAX(a,b) ((a)>(b)?(a):(b))
  22. #define MIN(a,b) ((a)>(b)?(b):(a))
  23. #define ABS(a) ((a)>0? (a):(-(a)))
  24. #define SQ(a) ((a)*(a))
  25. #define SZ(a) (int)a.size()
  26. #define FORN(i,n) for(i=1;i<=n;i++)
  27. #define FORAB(i,a,b) for(i=a;i<=b;i++)
  28. #define ALL(V) V.begin(),V.end()
  29. #define pb(a) push_back(a)
  30. #define pr(a) cout<<a<<endl
  31. #define pf printf
  32. #define sf scanf
  33. #define swap(a,b) (a ^= b, b ^= a, a ^= b)
  34. #define PI 2*acos(0)
  35. #define x first
  36. #define y second
  37. #define eps 1e-9
  38. #define MX 50001
  39.  
  40. typedef int D;
  41. typedef long long int LLD;
  42. typedef unsigned long long int LLU;
  43. typedef vector<D> VI;
  44. typedef set<D> SI;
  45. typedef vector<D>::iterator Viti;
  46.  
  47. /***********Template Ends Here***********/
  48.  
  49. int i,N;
  50.  
  51. double X[MX],Y[MX],Z[MX],L,R,lx,ry;
  52.  
  53. pair<double,double>P;
  54.  
  55. bool isvalid(double h)
  56. {
  57.     vector<pair<double,double> >V;
  58.     for(i=0; i<N; i++)
  59.     {
  60.         if(Y[i]>=h+eps)
  61.         {
  62.             P.x=X[i]-tan(Z[i])*(Y[i]-h);
  63.             P.y=X[i]+tan(Z[i])*(Y[i]-h);
  64.             V.pb(P);
  65.         }
  66.     }
  67.     if(V.size()==0) return false;
  68.     sort(ALL(V));
  69.     lx=V[0].x;
  70.     ry=V[0].y;
  71.     for(i=1; i<SZ(V); i++)
  72.     {
  73.         if(V[i].x<=ry)
  74.             ry=MAX(ry,V[i].y);
  75.         else
  76.         {
  77.             if(L>=lx && R<=ry)
  78.                 return true;
  79.             lx=V[i].x;
  80.             ry=V[i].y;
  81.         }
  82.     }
  83.     return L>=lx && R<=ry;
  84. }
  85.  
  86. int main()
  87. {
  88.     double low,high,mid,result;
  89.     cin>>N>>L>>R;
  90.     for(i=0; i<N; i++)
  91.     {
  92.         cin>>X[i]>>Y[i]>>Z[i];
  93.         Z[i]=Z[i]*PI/180;
  94.     }
  95.     low=0;
  96.     high=1000;
  97.     while((ABS(high-low))>eps)
  98.     {
  99.         mid=(low+high)/2.0;
  100.         if(isvalid(mid))
  101.             low=mid;
  102.         else
  103.             high=mid;
  104.     }
  105.     result=(low+high)/2.0;
  106.     result+=eps;
  107.     printf("%.10lf\n",result);
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment