Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. /* Najbliższa para punktów
  2.  */
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <climits>
  6. #include <algorithm>
  7. #include <list>
  8.  
  9. using namespace std;
  10.  
  11. struct Point {
  12.     double x,y;
  13.     bool operator< (const Point& b) const {
  14.         if( x == b.x )
  15.             return y < b.y;
  16.         return x < b.x;
  17.     }
  18. };
  19.  
  20.  
  21. bool compare( const Point& a, const Point& b ) {
  22.         if( a.y == b.y )
  23.             return a.x < b.x;
  24.         return a.y < b.y;
  25. }
  26.  
  27.  
  28. double length( const Point& a, const Point& b ) {
  29.     double xx = a.x-b.x;
  30.     double yy = a.y-b.y;
  31.     return xx*xx + yy*yy;
  32. }
  33.  
  34. double length( const double a, const double b ) {
  35.     double c = a-b;
  36.     if( c < 0 )
  37.         c = -c;
  38.     return c;
  39. }
  40.  
  41. list< int > L;
  42.  
  43.  
  44. double alg(Point T[], int n) {  // na wejsciu punkty posortowane po X
  45.     if( n < 2 ) return 10e100;  // mniej niż 2 punkty zwracaja nieskonczonosc
  46.     int m = n/2; // Dziel i zwycięzaj
  47.     int i;
  48.     double l = T[m].x; // Granica miedzy lewa i prawa polowa
  49.     double d = min(    // Najlepszy wynik(^2) zawierajacy sie w polowkach
  50.         alg( T, m ),   // Uwaga, alg() sortuje, wiec l trzeba odczytac wczesniej
  51.         alg( T+m, n-m )
  52.     );
  53.     inplace_merge( T, T+m, T+n, compare );  // na wyjsciu sortujemy po Y
  54.     L.clear();
  55.     double dd = sqrt(d); // Najlepszy wynik
  56.     for( i = 0; i < n; i++ )
  57.         if( length( T[i].x,l ) <= dd )
  58.             L.push_back( i ); // Dodajemy wszystkie punkty odlegle od l nie wiecej niz dd
  59.  
  60.     list< int >::iterator it, that;
  61.     for( it = L.begin(); it != L.end(); it++ ) {
  62.         for( that = it, i=1; ++that != L.end(); ) { // tu powinno byc ograniczenie dot. nie sprawdzania punktow lezacych zbyt nisko
  63.             double m = length( T[ *it ], T[ *that ] ); // mądre twierdzenie glosi ze takich punktow bedzie nie wiecej niz 5
  64.             if( m < d )
  65.                 d = m;
  66.         }
  67.     }
  68.     return d;
  69. }
  70.  
  71. Point T[10010];
  72.  
  73. int n;
  74. void solve() {
  75.     FILE *in,*out;
  76.  
  77.     in=fopen("In02.txt","r");
  78.     fscanf(in,"%d",&n);
  79.  
  80.     for( int i = 0; i < n; i++ ) {
  81.          fscanf(in,"%d %d", &T[i].x, &T[i].y );
  82.          printf("%d %d \n",T[i].x,T[i].y);
  83.     }
  84.     fclose(in);
  85.     sort( T, T+n );
  86.     double a = sqrt(alg(T, n));
  87.     if( a < 10000 )
  88.         printf("%.4lf\n", a);
  89.     else
  90.         printf("INFINITY\n");
  91. }
  92.  
  93. int main() {
  94.     int T=2;
  95.         solve();
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement