Submission #3828

#	Time	Username	Problem	Language	Result	Execution time	Memory
3828		sjw0687	Divide into triangle (kriii1_D)	C++98	0 / 1	0 ms	1688 KiB

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;
}

vector< int > giftWrap(vector< pair<int, vector2> >& points)
{
	int n = points.size();
	vector< pair<int, vector2> > hull;
	vector< int > rm;
	vector< pair<int, vector2> >::iterator pivot = min_element(points.begin(), points.end(), paIntVec2Comp);
	hull.push_back( *pivot );
	rm.push_back( pivot - points.begin() );
	while( hull.size() < 3 ) {
		vector2 ph = hull.back().second, next = points[0].second;
		int nextInt = 0;
		for(int i=1; i<n; i++) {
			double cross = ccw(ph, next, points[i].second);
			double dist = (next - ph).norm() - (points[i].second - ph).norm();
			if(cross > 0 || (cross == 0 && dist < 0)) {
				next = points[i].second;
				nextInt = i;
			}
		}
		if(next == pivot->second) break;
		hull.push_back( make_pair(nextInt, next) );
		rm.push_back( nextInt );
	}
	sort(rm.begin(), rm.end());
	return rm;
}

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;
	}

	while( points.size() > 0 ) {
		vector< int > rm = giftWrap(points);
		cout << points[rm[0]].first << ' ' << points[rm[1]].first << ' ' << points[rm[2]].first << endl;
		for(int i=2; i>=0; i--) {
			points.erase( points.begin() + rm[i] );
		}
	}

	return 0;
}

• Subtask 1: 0 / 1