Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Najbliższa para punktów
- */
- #include <cstdio>
- #include <cmath>
- #include <climits>
- #include <algorithm>
- #include <list>
- using namespace std;
- struct Point {
- double x,y;
- bool operator< (const Point& b) const {
- if( x == b.x )
- return y < b.y;
- return x < b.x;
- }
- };
- bool compare( const Point& a, const Point& b ) {
- if( a.y == b.y )
- return a.x < b.x;
- return a.y < b.y;
- }
- double length( const Point& a, const Point& b ) {
- double xx = a.x-b.x;
- double yy = a.y-b.y;
- return xx*xx + yy*yy;
- }
- double length( const double a, const double b ) {
- double c = a-b;
- if( c < 0 )
- c = -c;
- return c;
- }
- list< int > L;
- double alg(Point T[], int n) { // na wejsciu punkty posortowane po X
- if( n < 2 ) return 10e100; // mniej niż 2 punkty zwracaja nieskonczonosc
- int m = n/2; // Dziel i zwycięzaj
- int i;
- double l = T[m].x; // Granica miedzy lewa i prawa polowa
- double d = min( // Najlepszy wynik(^2) zawierajacy sie w polowkach
- alg( T, m ), // Uwaga, alg() sortuje, wiec l trzeba odczytac wczesniej
- alg( T+m, n-m )
- );
- inplace_merge( T, T+m, T+n, compare ); // na wyjsciu sortujemy po Y
- L.clear();
- double dd = sqrt(d); // Najlepszy wynik
- for( i = 0; i < n; i++ )
- if( length( T[i].x,l ) <= dd )
- L.push_back( i ); // Dodajemy wszystkie punkty odlegle od l nie wiecej niz dd
- list< int >::iterator it, that;
- for( it = L.begin(); it != L.end(); it++ ) {
- for( that = it, i=1; ++that != L.end(); ) { // tu powinno byc ograniczenie dot. nie sprawdzania punktow lezacych zbyt nisko
- double m = length( T[ *it ], T[ *that ] ); // mądre twierdzenie glosi ze takich punktow bedzie nie wiecej niz 5
- if( m < d )
- d = m;
- }
- }
- return d;
- }
- Point T[10010];
- int n;
- void solve() {
- FILE *in,*out;
- in=fopen("In02.txt","r");
- fscanf(in,"%d",&n);
- for( int i = 0; i < n; i++ ) {
- fscanf(in,"%d %d", &T[i].x, &T[i].y );
- printf("%d %d \n",T[i].x,T[i].y);
- }
- fclose(in);
- sort( T, T+n );
- double a = sqrt(alg(T, n));
- if( a < 10000 )
- printf("%.4lf\n", a);
- else
- printf("INFINITY\n");
- }
- int main() {
- int T=2;
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement