【HDU-6300】解题报告（简单几何贪心）

原始题目

Triangle Partition

  • Time Limit: 2000/1000 MS (Java/Others)
  • Memory Limit: 132768/132768 K (Java/Others)
  • Total Submission(s): 1054
  • Accepted Submission(s): 533
  • Special Judge

Problem Description

Chiaki has \(3n\) points \(p\_1,p\_2,…,p\_{3n}\). It is guaranteed that no three points are collinear.

Chiaki would like to construct \(n\) disjoint triangles where each vertex comes from the \(3n\) points.

Input

There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:

The first line contains an integer \(n (1≤n≤1000)\) -- the number of triangle to construct.

Each of the next 3n lines contains two integers \(x\_i\) and \(y\_i (−109≤x\_i,y\_i≤109)\).

It is guaranteed that the sum of all \(n\) does not exceed 10000.

Output

For each test case, output \(n\) lines contain three integers \(a\_i,b\_i,c\_i (1≤a\_i,b\_i,c\_i≤3n)\) each denoting the indices of points the i-th triangle use. If there are multiple solutions, you can output any of them.

Sample Input

1
1
1 2
2 3
3 5

Sample Output

1 2 3

Source

2018 Multi-University Training Contest 1

Recommend

liuyiding

题目大意

给出\(3n\)个点，且任意三点军部贡献，要求按顺序给出\(n\)个三角形的三个顶点坐标，要求\(n\)个三角形两两不相交（不共点）。

解题思路

反向理解 若两条线相交（如下图）

假设我们连三角形时先连A线再连，B线，若出现A2>B1，则有可能会出现两线相交。

考虑到题目给出任意三点不共线，即人以三点都可以构成一个三角形。我们只要找到一种方法逐个连接出不相交的三角形就行。

按x轴将所有点排序，从小到大每次找三个点即可。

#解题代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size()) 
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int maxn=1e4+5;

struct node{
	int index;
	pii point;
}a[maxn];


ll t,n,m;
bool cmp(node a, node b){
	if(a.point.first==b.point.first) 
		return a.point.second<b.point.second;
	else return a.point.first<b.point.first;
}
int main(){
	ios::sync_with_stdio(false);	
	cin>>t;
	while(t--){
		cin>>n;
		rep(i,1,3*n+1){
			a[i].index=i;
			cin>>a[i].point.first>>a[i].point.second;
		
		}
		sort(a+1,a+1+3*n,cmp);
//		rep(i,1,3*n+1){
//			cout<<a[i].point.fi<<" "<<a[i].point.se<<endl;
//		}
		rep(i,1,3*n+1){
			if(i==1) cout<<a[i].index;
			else cout<<" "<<a[i].index;
		}
		cout<<endl;
		
	}
	
}

收获与反思

  • 简单的几何贪心，考虑两线相交的条件拓展即可。