Submission #3875

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3875	2013-08-31T09:01:35 Z	sjw0687	Divide into triangle (kriii1_D)	C++	1 / 1	4 ms	1692 KB

D

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;

struct vector2 {
	double x, y;
	vector2(double _x = 0, double _y = 0) : x(_x), y(_y) {}

	bool operator == (vector2& rhs) {
		return x == rhs.x && y == rhs.y;
	}

	bool operator < (vector2& rhs) {
		return x != rhs.x ? x < rhs.x : y < rhs.y;
	}

	vector2 operator + (vector2& rhs) {
		return vector2(x + rhs.x, y + rhs.y);
	}

	vector2 operator - (vector2& rhs) {
		return vector2(x - rhs.x, y - rhs.y);
	}

	double norm() {
		return hypot(x, y);
	}

	double cross(vector2& rhs) {
		return x * rhs.y - rhs.x * y;
	}
};

typedef vector<vector2> polygon;

double ccw(vector2 a, vector2 b)
{
	return a.cross(b);
}

double ccw(vector2 p, vector2 a, vector2 b)
{
	return ccw(a-p, b-p);
}

bool paIntVec2Comp(pair<int, vector2> a, pair<int, vector2> b)
{
	return a.second < b.second;
}

polygon giftWrap(vector<vector2>& points)
{
	int n = points.size();
	polygon hull;
	vector2 pivot = *min_element(points.begin(), points.end());
	hull.push_back(pivot);
	while(true) {
		vector2 ph = hull.back(), next = points[0];
		for(int i=1; i<n; i++) {
			double cross = ccw(ph, next, points[i]);
			double dist = (next - ph).norm() - (points[i] - ph).norm();
			if(cross > 0 || (cross == 0 && dist < 0))
				next = points[i];
		}
		if(next == pivot) break;
		hull.push_back(next);
	}
	return hull;
}

int main(void)
{
	int n;
	cin >> n;
	vector< pair<int, vector2> > points(3*n);
	for(int i=0; i<3*n; i++) {
		points[i].first = i+1;
		cin >> points[i].second.x >> points[i].second.y;
	}

	sort(points.begin(), points.end(), paIntVec2Comp);
	for(int i=0; i<3*n; i+=3) {
		cout << points[i].first << ' ' << points[i+1].first << ' ' << points[i+2].first << endl;
	}

	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1692 KB	Output is correct
2	Correct	0 ms	1692 KB	Output is correct
3	Correct	0 ms	1692 KB	Output is correct
4	Correct	0 ms	1692 KB	Output is correct
5	Correct	0 ms	1692 KB	Output is correct
6	Correct	0 ms	1692 KB	Output is correct
7	Correct	0 ms	1692 KB	Output is correct
8	Correct	0 ms	1692 KB	Output is correct
9	Correct	0 ms	1692 KB	Output is correct
10	Correct	0 ms	1692 KB	Output is correct
11	Correct	4 ms	1692 KB	Output is correct
12	Correct	4 ms	1692 KB	Output is correct
13	Correct	4 ms	1692 KB	Output is correct
14	Correct	0 ms	1692 KB	Output is correct
15	Correct	0 ms	1692 KB	Output is correct
16	Correct	4 ms	1692 KB	Output is correct
17	Correct	0 ms	1692 KB	Output is correct
18	Correct	4 ms	1692 KB	Output is correct
19	Correct	0 ms	1692 KB	Output is correct
20	Correct	0 ms	1692 KB	Output is correct