UVa : 478


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define N 1000000
using namespace std;

struct figure {
    char f;
    double point [6];
} a [10 + 2];

double triangleArea ( double xa, double ya, double xb, double yb, double xc, double yc )
{
    double temp = (xa - xc) * (yb - ya) - (xa - xb) * (yc - ya);
    if ( temp < 0 )
        temp *= -1;
    temp /= 2;

    return temp;
}

bool pointContained (double x, double y, int ith)
{
    if ( a [ith].f == 'r' ) {
        if ( x > a [ith].point [0] && x < a [ith].point [2] && y < a [ith].point [1] && y > a [ith].point [3] )
            return true;
    }
    else if ( a [ith].f == 'c' ) {
        double distance = sqrt (pow(x - a [ith].point [0], 2) + pow (y - a [ith].point [1], 2));
        if ( distance < a [ith].point [2] )
            return true;
    }
    else {
        double totalArea = triangleArea ( a [ith].point [0], a [ith].point [1], a [ith].point [2],
        a [ith].point [3], a [ith].point [4], a [ith].point [5] );

        double abd = triangleArea ( a [ith].point [0], a [ith].point [1], a [ith].point [2],
        a [ith].point [3], x, y );

        double acd = triangleArea ( a [ith].point [0], a [ith].point [1], x, y, a [ith].point [4], a [ith].point [5] );

        double bcd = triangleArea ( x, y, a [ith].point [2],
        a [ith].point [3], a [ith].point [4], a [ith].point [5] );

        if ( fabs (totalArea - (abd + acd + bcd)) < 1e-5 && abd != 0 && acd != 0 && bcd != 0 )
        //if ( abd + acd + bcd == totalArea && abd != 0 && acd != 0 && bcd != 0 )
            return true;
    }

    return false;
}

int main ()
{
    char input [5];
    int index = 0;

    while ( scanf ("%s", input) && strcmp (input, "*") != 0 ) {
        if ( strcmp (input, "r") == 0 ) {
            a [index].f = 'r';
            cin >> a [index].point [0] >> a [index].point [1] >> a [index].point [2] >> a [index].point [3];
        }
        else if ( strcmp (input, "c") == 0 ) {
            a [index].f = 'c';
            cin >> a [index].point [0] >> a [index].point [1] >> a [index].point [2];
        }
        else {
            a [index].f = 't';
            cin >> a [index].point [0] >> a [index].point [1] >> a [index].point [2];
            cin >> a [index].point [3] >> a [index].point [4] >> a [index].point [5];
        }
        index++;
    }

    double x;
    double y;
    int points = 1;

    while ( cin >> x >> y && x != 9999.9 && y != 9999.9 ) {
        bool printed = false;
        for ( int i = 0; i < index; i++ ) {
            if ( pointContained (x, y, i) ) {
                printf ("Point %d is contained in figure %d\n", points, i + 1);
                printed = true;
            }
        }

        if ( printed == false )
            printf ("Point %d is not contained in any figure\n", points);

        points++;
    }


    return 0;
}

// @END_OF_SOURCE_CODE
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