lib/Documentation/docs-sonyckson/11355.cpp

   1 // PORCENTAJE VISIBLE DESDE EL CENTRO DE UN CIRCULO; ANTE VARIOS SEGMENTOS :)
   2 // ACLARACIÖN: MISTERIOSAMENTE NO FUNCIONO EL PRODUCTO CRUZ....
   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-9
  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 main(){
  58         int i,j ,k;
  59         int casos;scanf("%i", &casos);
  60         double R;
  61         for(int h = 0 ; h < casos;h++){
  62                 scanf("%i %lf", &n, &R);
  63                 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);
  64                 vector<pair<double,double> > intervalo;
  65                 for(i=0;i<n;i++) intervalo.push_back(inter(seg[i]));
  66                 for(i=0;i<intervalo.size();i++){
  67                         if( intervalo[i].first < intervalo[i].second){
  68                                 if( intervalo[i].second-intervalo[i].first  > PI)
  69                                         swap(intervalo[i].first, intervalo[i].second);
  70                         }else{
  71                                 if( intervalo[i].first-intervalo[i].second  < PI )
  72                                         swap(intervalo[i].first, intervalo[i].second);
  73                         }
  74                 }
  75                 for(i=0;i<intervalo.size();i++) if( intervalo[i].first > EPS+intervalo[i].second){
  76                         intervalo[i].second += 2.0*PI;
  77                 }
  78                 sort(intervalo.begin(), intervalo.end());
  79                 while(borrar(intervalo));
  80                 double tot = 0.0;
  81                 for(i=0;i<intervalo.size();i++)
  82                         tot+=intervalo[i].second-intervalo[i].first;
  83                 tot = min(M, tot);
  84                 printf("Case %i: %.2lf%%\n", h+1, 100.0*(1.0-tot/M));
  85         }return 0;
  86 }