lib/Documentation/docs-sonyckson/3954.cpp

   1 #include <cstdio>
   2 #include <vector>
   3 #include <utility>
   4 #include <cmath>
   5 #include <cstdlib>
   6 #include <string>
   7 #include <iostream>
   8 #include <algorithm>
   9 using namespace std;
  10 int N;double R;
  11 #define D double
  12 #define EPS 1e-9
  13 #define PB push_back
  14 vector<pair<D,D> > point;
  15 int res;
  16 double hypot(double x, double y){
  17         return sqrt(x*x+y*y);
  18 }
  19 double cruz(pair<D,D> p1, pair<D,D> p2, pair<D,D> p3){
  20         double x1, x2, y1, y2;
  21         x1 = p2.first - p1.first, x2 = p3.first - p1.first;
  22         y1 = p2.second - p1.second, y2 = p3.second - p1.second;
  23         return acos( (x1*x2+y1*y2)/(hypot(x1,y1)*hypot(x2,y2)));
  24 }
  25 double dist(pair<D,D> p1, pair<D,D> p2){
  26         double dx, dy;
  27         dx = p2.first -p1.first, dy = p2.second - p1.second;
  28         return hypot(dx,dy);
  29 }
  30 #define Y second
  31 #define X first
  32 pair<D,D> P;
  33 bool menor(pair<pair<D,D>,int> p1, pair<pair<D,D>,int> p2){
  34         double c = cruz(P, p1.first,p2.first);
  35         if( fabs(c) < EPS ) return false;
  36         return c < 0.;
  37 }
  38 void PROVE(vector<pair<D,D> > &vec, pair<D,D> p){
  39         vector<pair<double,int> > interval;
  40         int i,j ,k;
  41         int cant = 0;
  42         for(k=0;k<vec.size();k++){
  43                 D xmed, ymed;
  44                 xmed = (p.first+vec[k].first)/2., ymed = (p.second+vec[k].second)/2.;
  45                 // calculamos la alturita del triángulo...
  46                 D d = dist(make_pair(xmed,ymed),p);
  47                 D altura = sqrt(max(R*R-d*d,0.));
  48                 D xch, ych;
  49                 xch = vec[k].second-ymed;
  50                 ych = xmed-vec[k].first;
  51                 xch /= d, ych/=d;
  52                 xch *= altura, ych *= altura;
  53
  54                 pair<D,D> p1, p2;
  55                 p1.first = xmed+xch; //min(p.first,xmed + xch);
  56                 p2.first = xmed-xch; //min(p.first,xmed - xch);
  57                 p1.second = ymed + ych;
  58                 p2.second = ymed - ych;
  59                 double c1, c2;
  60                 c1 = cruz(p,p1,make_pair(p.X,10000000000000.));
  61                 c2 = cruz(p,p2,make_pair(p.X,10000000000000.));
  62                 double V = acos(-1);
  63                 if( p1.first > p.first ) c1 = 2.*V-c1;
  64                 if( p2.first > p.first ) c2 = 2.*V-c2;
  65                 if( p1.first > p.first && p2.first < p.first ){
  66                         if( vec[k].second > p.second ) cant++;
  67
  68                 }
  69                 interval.push_back(make_pair(c1,-1));
  70                 interval.push_back(make_pair(c2,1));
  71         }
  72         sort(interval.begin(), interval.end());
  73         int c = cant;
  74         for(i=(int)interval.size()-1;i>=0;i--){
  75                 res = max ( res, abs(c) );
  76                 c += interval[i].second;
  77         }
  78 }
  79 int main(){
  80         int i,j ,k;
  81         while(1){
  82                 scanf("%i %lf", &N, &R);
  83                 if(!N) return 0;
  84                 point.clear();
  85                 for(i=0;i<N;i++){D x, y; scanf("%lf %lf", &x, &y); point.push_back(make_pair(x,y));}
  86
  87                 sort(point.begin(), point.end());
  88
  89                 res = 0;
  90
  91                 R+= 0.001;
  92                 for(i=0;i<point.size();i++){
  93                         vector<pair<D,D> > AUX;
  94                         for(j=0;j<point.size();j++){
  95                                 if( j == i ) continue;
  96                                 if( dist(point[i], point[j]) > 2.* R ) continue;
  97                                 AUX.push_back(point[j]);
  98                         }
  99                         PROVE(AUX, point[i]);
 100                 }
 101                 printf("It is possible to cover %i points.\n", res+1);
 102         }return 0;
 103 }