Documentation/docs-sonyckson/11382.cpp

   1 // CALCULAR EL MINIMO ANGULO PARA EL ARMA QUE CON HASTA K TIROS MATA A TODOS
   2 // LOS SEGMENTOS; ( FANTASMITAS :P ES COMO GHOSTBUSTERS :P )
   3 #include <cstdio>
   4 #include <cmath>
   5 #include <algorithm>
   6 #include <vector>
   7 #include <utility>
   8 using namespace std;
   9 typedef struct{
  10         double x, y;
  11 }point;
  12 typedef struct{
  13         point p1, p2;
  14 }segment;
  15 int n;
  16 segment seg[101];
  17 double M = 2*acos(-1);
  18 double PI = acos(-1);
  19 #define EPS 1e-7
  20 double angulo(point p){
  21         double d = sqrt(p.x*p.x+p.y*p.y);
  22         p.x /= d;
  23         p.y /= d;
  24         double angle = acos(p.x);
  25         if( p.y + EPS< 0.0 ) angle = 2.0*PI-angle;
  26         return angle;
  27 }
  28 pair<double,double> inter(segment seg){
  29         return make_pair(angulo(seg.p1), angulo(seg.p2));
  30 }
  31 int borrar(vector<pair<double,double> > &vec){
  32         if( vec.size() == 1 ) return 0;
  33         for(int i=0;i<vec.size();i++){
  34                 if( fabs(vec[i].first-vec[i].second) < EPS ){
  35                         vec.erase(vec.begin()+i);
  36                         return 1;
  37                 }
  38                 int next = (i+1)%vec.size();
  39                 if( next ){
  40                         if(  vec[next].first < vec[i].second ){
  41                                 vec[i].second = max(vec[i].second, vec[next].second);
  42                                 vec.erase(vec.begin()+next);
  43                                 return 1;
  44                         }
  45                 }else{
  46                         pair<double, double> par = vec[next];
  47                         par.first+=2.0*PI, par.second+=2.0*PI;
  48                         if( par.first < vec[i].second ){
  49                                 vec[i].second = max(vec[i].second, par.second);
  50                                 vec.erase(vec.begin()+next);
  51                                 return 1;
  52                         }
  53                 }
  54         }
  55         return 0;
  56 }
  57 int tratar(vector<pair<double, double> >  vec, int ind, double dist){
  58         int i,j ,k;
  59         double last = vec[ind].first;
  60         int listo = 0;
  61         i = ind;int first=0;
  62         int res = 0;
  63         while(!listo){
  64                 if( i == ind ){
  65                         if(first)break;
  66                         else first=1;
  67                 }
  68                 if( i == 0 && last > M ){
  69                         while(last > M )last -= M;
  70                 }else if( i == 0 ) last = 0.0;
  71                 double pri, sec;
  72                 pri = max(vec[i].first, last);
  73                 sec = vec[i].second;
  74                 if( pri < sec ){
  75                         double len = ((sec-pri)/dist);
  76                         int ca;
  77                         if( fabs(len-floor(len+EPS)) < EPS ) ca = (int)(len+EPS);
  78                         else ca = (int)(len+EPS)+1;
  79                         res+=ca;
  80                         last = pri+dist*(double)ca;
  81                 }
  82                 i = (i+1)%vec.size();
  83         }
  84         return res;
  85 }
  86 int cantidad(double dist, vector<pair<double, double> > vec){
  87         int i,j ,k;
  88         int res = 100000;
  89         for(i=0;i<vec.size();i++)  res = min(tratar(vec, i, dist), res);
  90         return res;
  91 }
  92 int main(){
  93         int i,j ,k;
  94         int casos;scanf("%i", &casos);
  95         double R;
  96         int K;
  97         for(int h = 0 ; h < casos;h++){
  98                 scanf("%i %i", &n, &K);
  99                 double x, y;
 100                 scanf("%lf %lf", &x, &y);
 101                 for(i=0;i<n;i++)scanf("%lf %lf %lf %lf", &seg[i].p1.x, &seg[i].p1.y, &seg[i].p2.x, &seg[i].p2.y);
 102                 for(i=0;i<n;i++){
 103                         seg[i].p1.x -= x;
 104                         seg[i].p2.x -= x;
 105                         seg[i].p1.y -= y;
 106                         seg[i].p2.y -= y;
 107                 }
 108                 vector<pair<double,double> > intervalo;
 109                 for(i=0;i<n;i++) intervalo.push_back(inter(seg[i]));
 110                 for(i=0;i<intervalo.size();i++){
 111                         if( intervalo[i].first < intervalo[i].second){
 112                                 if( intervalo[i].second-intervalo[i].first  > PI)
 113                                         swap(intervalo[i].first, intervalo[i].second);
 114                         }else{
 115                                 if( intervalo[i].first-intervalo[i].second  < PI )
 116                                         swap(intervalo[i].first, intervalo[i].second);
 117                         }
 118                 }
 119                 for(i=0;i<intervalo.size();i++) if( intervalo[i].first > EPS+intervalo[i].second){
 120                         intervalo[i].second += 2.0*PI;
 121                 }
 122                 sort(intervalo.begin(), intervalo.end());
 123                 while(borrar(intervalo));
 124                 double tot = 0.0;
 125                 for(i=0;i<intervalo.size();i++)
 126                         tot+=intervalo[i].second-intervalo[i].first;
 127                 tot = min(M, tot);
 128                 double res;
 129                 if( fabs(tot-M) < EPS ){
 130                         if( K == 1 ) res = -1.0;
 131                         else res = M / (double) K ;
 132                 }else{
 133                         double b, e;
 134                         b = (1.0/180.0)*PI;
 135                         e = PI;
 136                         if( cantidad(e, intervalo) > K ) res = -1.0;
 137                         else if( cantidad(b,intervalo) <= K )res = b;
 138                         else {
 139                                 while( fabs( b-e ) > EPS/2.0 ){
 140                                         double med = (b+e)/2.0;
 141                                         if( cantidad(med, intervalo) <= K ){
 142                                                 e = med;
 143                                         }else b = med;
 144                                 }
 145                                 res = e;
 146                         }
 147                 }
 148                 if( res > -0.01 ){
 149                         res = (res/PI)*180.0;
 150                         res = max(res, 1.0);
 151                 }
 152                 printf("%.4lf\n", res);
 153         }return 0;
 154 }