UVa 478 - Points in Figures: Rectangles, Circles, Triangles

// UVa 478 - Points in Figures: Rectangles, Circles, Triangles

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

struct rectangle {
	double x1, x2, y1, y2;
};

struct circle {
	double r, x, y;
};

struct triangle {
	double x1, x2, x3, y1, y2, y3;
};

char fig[11];
circle c[11];
rectangle r[11];
triangle t[11];

double cross(double x0, double y0, double x1, double y1, double x2, double y2) {
	x1 -= x0;
	y1 -= y0;
	x2 -= x0;
	y2 -= y0;
	return x1 * y2 - x2 * y1;
}

double dist(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool inside(double x, double y, circle c) {
	return (dist(x, y, c.x, c.y) < c.r);
}

bool inside(double x, double y, rectangle r) {
	return r.x1 < x && x < r.x2 && r.y1 < y && y < r.y2;
}

bool inside(double x, double y, triangle t) {
	double w1 = cross(t.x1, t.y1, t.x2, t.y2, x, y);
	double w2 = cross(t.x2, t.y2, t.x3, t.y3, x, y);
	double w3 = cross(t.x3, t.y3, t.x1, t.y1, x, y);
	return (w1 * w2 > 0) && (w1 * w3 > 0) && (w2 * w3 > 0);
}

int main() {
	string l;
	int n = 0;
	while (getline(cin, l) && l[0] != '*') {
		n++;
		fig[n] = l[0];
		istringstream strm(l.substr(2));
		switch (l[0]) {
		case 'r':
			strm >> r[n].x1 >> r[n].y2 >> r[n].x2 >> r[n].y1;
			if (r[n].x1 > r[n].x2) {
				double tmp = r[n].x1;
				r[n].x1 = r[n].x2;
				r[n].x2 = tmp;
			}
			if (r[n].y1 > r[n].y2) {
				double tmp = r[n].y1;
				r[n].y1 = r[n].y2;
				r[n].y2 = tmp;
			}
			break;
		case 'c':
			strm >> c[n].x >> c[n].y >> c[n].r;
			break;
		case 't':
			strm >> t[n].x1 >> t[n].y1 >> t[n].x2 >> t[n].y2 >> t[n].x3 >> t[n].y3;
			break;
		}
	}
	int m = 0;
	double x, y;
	while (cin >> x >> y && (9999.9 != x || 9999.9 != y)) {
		m++;
		bool free = true;
		for (int i = 1; i <= n; i++) {
			bool contained = false;
			switch (fig[i]) {
			case 'r':
				if (inside(x, y, r[i]))
					contained = true;
				break;
			case 'c':
				if (inside(x, y, c[i]))
					contained = true;
				break;
			case 't':
				if (inside(x, y, t[i]))
					contained = true;
				break;
			}
			if (contained) {
				printf("Point %d is contained in figure %d\n", m, i);
				free = false;
			}
		}
		if (free)
			printf("Point %d is not contained in any figure\n", m);
	}
	return 0;
}