Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Radar Installation - UVA 1193

By: tcbpg on Jul 30th, 2012  |  syntax: C++  |  size: 1.91 KB  |  hits: 41  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdlib>
  11. #include <cmath>
  12. #include <bitset>
  13.  
  14. using namespace std;
  15.  
  16. #define forn(i,n) for(int i=0;i<(int)(n);i++)
  17. #define forsn(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
  18. #define forall(i,c) for(typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
  19. #define dforn(i,n) for(int i=((int)(n)-1);i>=0;i--)
  20. #define dforsn(i,s,n) for(int i=((int)(n)-1);i>=(int)(n);i--)
  21. #define esta(i,c) ((c).find(i) != (c).end())
  22. #define estal(i,c) (find((c).begin(),(c).end(),(i))!=(c).end())
  23. #define all(c) (c).begin(),(c).end()
  24.  
  25. #define dbg(x) cerr << #x << " = " << x << endl;
  26. #define raya cerr << string(80,'=') << endl;
  27.  
  28. typedef long long tint;
  29. typedef pair<int,int> pii;
  30. typedef vector<int> vi;
  31. typedef vector< pair<int,int> > vii;
  32.  
  33. const int MAXN = 10000;
  34. const double eps = 1e-10;
  35. struct Interval{
  36.         double st,en;
  37.         Interval(){}
  38.         Interval(double s, double e){
  39.                 st = s, en = e;
  40.         }
  41.         bool operator<(const Interval & i) const{
  42.                 return (i.en == en) ? (st < i.st) : (en < i.en);
  43.         }
  44. };
  45. long double x[MAXN],y[MAXN];
  46. Interval inter[MAXN];
  47. int main(){
  48.         #ifdef JUAMPI
  49.                 freopen("1193.in","r",stdin);
  50.         #endif
  51.         int n,d, testcase = 0;
  52.         while(scanf("%d%d",&n,&d) == 2 && !(n == 0 && d == 0)){
  53.                 forn(i,n) scanf("%Lf %Lf",&x[i],&y[i]);
  54.                 int count = 0, ok = true;
  55.                 forn(i,n){
  56.                         if(d < y[i]){
  57.                                 ok = false;
  58.                                 break;
  59.                         }else{
  60.                                 long double sqrtd = sqrt((1.0*d)*d-y[i]*y[i]);
  61.                                 inter[i] = Interval(x[i]-sqrtd,x[i]+sqrtd);
  62.                         }
  63.                 }
  64.                 if(!ok){
  65.                         printf("Case %d: %d\n",++testcase,-1);
  66.                         continue;
  67.                 }
  68.                 sort(inter,inter+n);
  69.  
  70.                 for(int i = 0; i < n;){
  71.                         int j;
  72.                         for(j = 0; j < n; j++){
  73.                                 if(inter[j].st - eps > inter[i].en)
  74.                                         break;
  75.                         }
  76.                         i = j; count++;
  77.                 }
  78.                 printf("Case %d: %d\n",++testcase,count);
  79.         }
  80.         return 0;
  81. }
create a new version of this paste RAW Paste Data