ACM (TJU) : 1905


#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    char ch;
    int x;
    int y;
} a [18];

double area (int p, int q, int r)
{
    double res;
    res = (a [r].y - a [p].y) * (a [q].x - a [p].x);
    res -=  (a [q].y - a [p].y) * (a [r].x - a [p].x);
    res *= 0.5;

    if ( res < 0 )
    res *= -1;

    return res;
}

int main ()
{
    int k [15];
    int dataSet;

    while ( cin >> dataSet && dataSet ) {

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

        for ( int i = 0; i < 15; i++ )
        k [i] = 0;

        k [0] = k [1] = k [2] = 1;

        sort (k, k + dataSet);
        double max = 0;
        double final;
        int t0, t1, t2;

        do {
            int z [3];
            int index = 0;
            bool result = true;

            for ( int i = 0; i < dataSet; i++ ) {
                if ( k [i] == 1 )
                    z [index++] = i;
            }

            for ( int i = 0; i < dataSet; i++ ) {
                if ( k [i] == 0 ) {
                    double first = area (i, z [0], z [1]);
                    double second = area (i, z [1], z [2]);
                    double third = area (i, z [0], z [2]);
                    final = area (z[0], z [1], z [2]);

                    if ( first + second + third == final ) {
                        result = false;
                        break;
                    }
                        //cout << a [z[0]].ch << a [z[1]].ch << a [z[2]].ch << endl;
                }
            }

            if ( result ) {
                if ( final > max ) {
                max = final;
                t0 = z [0];
                t1 = z [1];
                t2 = z [2];
                }
            }
            //cout << a [z[0]].ch << a [z[1]].ch << a [z[2]].ch << endl;

        } while ( next_permutation (k, k+dataSet));

        cout << a [t0].ch << a [t1].ch << a [t2].ch << endl;

    }

    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