Guest User

Untitled

a guest
Oct 17th, 2017
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <sstream>
  7.  
  8. using namespace std;
  9.  
  10. const double pi = acos(-1.0);
  11. const double EPS = 1e-9;
  12. const double INF = 1e50;
  13.  
  14. int cmp(double a, double b){ return fabs(a-b) < EPS ? 0 : ( a > b ? 1 : -1 ); }
  15.  
  16. //estrutura que representa um ponto
  17. // ou um vetor dependendo da necessidade
  18. struct pt{
  19.     double x, y;
  20.    
  21.     pt(double x = 0.0, double y = 0.0) : x(x), y(y) {}
  22.     double length() { return sqrt(x*x + y*y); }
  23.    
  24.     bool normalize(){
  25.         double l = length();
  26.         if(fabs(l) < EPS) //vetor nulo
  27.             return false;
  28.            
  29.         x /= l; y /= l;
  30.         return true;
  31.     }
  32.    
  33.     pt operator - (pt p){
  34.         return pt(x - p.x, y - p.y);
  35.     }
  36.     pt operator + (pt p){
  37.         return pt(x + p.x, y + p.y);
  38.     }
  39.     pt operator * (double k){
  40.         return pt(x * k, y * k);
  41.     }
  42.     pt operator / (double k){
  43.         return pt(x / k, y / k);
  44.     }
  45.    
  46.     bool operator < (const pt& p) const{
  47.         if(fabs( x - p.x ) >= EPS) return x < p.x;
  48.         return y < p.y;
  49.     }
  50.    
  51.     bool operator == (const pt p){
  52.         return ( fabs(x - p.x) < EPS && fabs(y - p.y) < EPS );
  53.     }
  54. };
  55.  
  56. double dist(pt a, pt b){
  57.     return (a - b).length();
  58. }
  59.  
  60. ////////////////////////////////////////////////////
  61.  
  62. double dot(pt a, pt b){
  63.     return a.x*b.x + a.y*b.y;
  64. }
  65.  
  66. double cross(pt a, pt b){
  67.     return a.x*b.y - a.y*b.x;
  68. }
  69.  
  70. //////////////////////////////////////////////////////
  71.  
  72. //testa se c esta na caixa limitada por a e b
  73. bool in_box(pt a, pt b, pt c){
  74.     return (c.x >= min(a.x, b.x)-EPS) && (c.x <= max(a.x, b.x)+EPS)
  75.         && (c.y >= min(a.y, b.y)-EPS) && (c.y <= max(a.y, b.y)+EPS);
  76. }
  77.  
  78. double signed_area(pt& a, pt& b, pt& c){
  79.     return cross((b-c),(a-c))/2.0;
  80. }
  81.  
  82. //interseccao entre as retas a->b e c->d e guarda em inter
  83. //retorna falso se sao paralelas
  84. //retorna (INF, INF) se sao coincidentes
  85. bool intersect(pt a, pt b, pt c, pt d, pt& inter){
  86.     double det = cross(b-a, d-c);
  87.     if(fabs(det) < EPS){
  88.         if( fabs(signed_area(a, b, c)) < EPS){
  89.             inter = pt(INF, INF);
  90.             return true; //retas coincidentes
  91.         }
  92.         return false; //retas paralelas
  93.     }
  94.     double ua = ( cross(d-c, a-c) )/det; //parametros das retas
  95.     //double ub = ( cross(b-a, a-c) )/det;
  96.     inter = a + (b-a)*ua;
  97.     return true;
  98. }
  99.  
  100. //testa se exsite interseccao entre os dois segmentos
  101. //retorna falso se nao ha intersecao
  102. //retorna (INF, INF) se os segmentos sao sobrepostos
  103. bool intersect_seg(pt a, pt b, pt c, pt d, pt& inter){
  104.     if( !intersect(a, b, c, d, inter) ) return false;
  105.    
  106.     if( inter.x == INF && inter.y == INF )
  107.         return in_box(a, b, min(c, d)) || in_box(c, d, min(a, b)); //segmentos sobrepostos
  108.        
  109.     return in_box(a, b, inter) && in_box(c, d, inter); //segmentos concorrentes
  110. }
  111.  
  112. //a->b para a->c
  113. double angle(pt a, pt b, pt c){
  114.     pt va = b-a, v = c-a;
  115.     va.normalize();
  116.     pt vb(-va.y, va.x);
  117.     return abs( atan2( dot(v, vb), dot(v, va) ) );
  118.     //retirar abs() para obter angulo orientado
  119. }
  120.  
  121. //determina o ponto mais proximo de c
  122. //na reta ab
  123. pt closest_point(pt a, pt b, pt c){
  124.     //se colinares
  125.     if( fabs( signed_area(a, b, c) ) < EPS) return c;
  126.    
  127.     pt v = b-a; v.normalize(); //ortogonal a ab
  128.     double pr = dot( v, c-a );
  129.     return ( a + (v*pr) );
  130. }
  131.  
  132. //determina o ponto mais proximo de c
  133. //no segmento ab
  134. pt closest_point_seg(pt a, pt b, pt c){
  135.     pt close = closest_point(a, b, c);
  136.     if( in_box(a, b, close) ) return close;
  137.     return dist(a, c) < dist(b, c) ? a : b;
  138. }
  139.  
  140. int main(){
  141.     ios::sync_with_stdio(false);
  142.     cout << fixed << setprecision(5);
  143.     double n, m, a;
  144.     double x, y;
  145.     pt pts[4], p;
  146.    
  147.     while(cin >> n >> a && fabs(n) > EPS){
  148.         m = 0;
  149.         pts[0] = pt(0, 0);
  150.         pts[1] = pt(0, a);
  151.         pts[2] = pt(a, 0);
  152.         pts[3] = pt(a, a);
  153.        
  154.         for(int i = 0; i < n; i++){
  155.             cin >> x >> y;
  156.             p = pt(x, y);
  157.            
  158.             if( cmp(dist(pts[0], p), a) <= 0 &&
  159.                 cmp(dist(pts[1], p), a) <= 0 &&
  160.                 cmp(dist(pts[2], p), a) <= 0 &&
  161.                 cmp(dist(pts[3], p), a) <= 0  )
  162.                 m++;
  163.         }
  164.        
  165.         cout << fixed << setprecision(5) << m*a*a/n << "\n";
  166.     }
  167.     return 0;
  168. }
Add Comment
Please, Sign In to add comment