狗狗40题搞完纪念 » 1011

1011
1011.cpp


#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

struct Point {
	int x, y;
};

int cross(const Point& p, const Point& a, const Point& b) {
	return (a.x - p.x) * (b.y - p.y) - (b.x - p.x) * (a.y - p.y);
}

int sameside(const Point& a, const Point& b, const Point& p, const Point& q) {
	return cross(p, a, b) * cross(q, a, b) > 0;
}

int intriangle(const Point& a, const Point& b, const Point& c, const Point& p) {
	return sameside(a, b, c, p) && sameside(b, c, a, p) && sameside(c, a, b, p);
}

int main() {
	Point a, b, c, p;
	int xmin, xmax, ymin, ymax;
	vector<int> x, y;

	puts("Program 4 by team X");
	while (scanf("%d%d%d%d%d%d", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y) != EOF) {
		xmin = min(min(a.x, b.x), c.x);
		xmax = max(max(a.x, b.x), c.x);
		ymin = min(min(a.y, b.y), c.y);
		ymax = max(max(a.y, b.y), c.y);
		x.clear();
		y.clear();
		for (p.x = xmin + 1; p.x < xmax; ++p.x) {
			for (p.y = ymin + 1; p.y < ymax; ++p.y) {
				if (intriangle(a, b, c, p)) {
					x.push_back(p.x);
					y.push_back(p.y);
				}
			}
		}

		xmin = *min_element(x.begin(), x.end());
		xmax = *max_element(x.begin(), x.end());
		ymin = *min_element(y.begin(), y.end());
		ymax = *max_element(y.begin(), y.end());
		for (p.y = ymax; p.y >= ymin; --p.y) {
			bool in = false;
			for (p.x = xmin; p.x <= xmax; ++p.x) {
				if (intriangle(a, b, c, p)) {
					in = true;
				} else if (in) {
					break;
				}
				if (p.x > xmin) {
					putchar(' ');
				}
				if (in) {
					printf("(%2d, %2d)", p.x, p.y);
				} else {
					printf("        ");
				}
			}
			puts("");
		}
		puts("");
	}
	puts("End of program 4 by team X");

	return 0;
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//257 	2010-06-25 00:08:29 	Accepted 	1011 	C++ 	10 	180 	anotherpeg 	Source
Leave a Reply