ACM (TJU) : 2856


#include <iostream>
#include <math.h>
using namespace std;

struct node {
    int x;
    int y;
    bool tagged;
} a [1005];

int n;

void reset ()
{
    for ( int i = 0; i < 1005; i++ ) {
        a [i].tagged = false;
    }
}

int main ()
{
    reset ();

    cin >> n;

    int untagged_cow = n;

    for ( int i = 0; i < n; i++ )
    cin >> a [i].x >> a [i].y;

    while ( untagged_cow != 1 ) {

        for ( int i = 0; i < n; i++ ) {

            if ( a [i].tagged == false ) {

                double min = 999999999;
                int save;

                for ( int j = 0; j < n; j++ ) {

                    if ( a [j].tagged == false && i != j ) {
                        double distance = sqrt (pow (a[j].x - a [i].x, 2) + pow (a[j].y - a [i].y, 2));
                        if ( distance < min ) {
                            min = distance;
                            save = j;
                        }
                    }
                }

                a [save].tagged = true;
                untagged_cow--;
            }
        }
    }

    // output
    for ( int i = 0; i < n; i++ ) {
        if ( a [i].tagged == false ) {
            cout << i + 1 << endl;
            break;
        }
    }

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s