CF618C Constellation 题解

题意描述

给定 \(n\) 个点（\(n\leq10^5\)），找到三个点满足这三个点不在同一直线上且三个点构成的三角形中不包含其他点，保证所有点不会在同一直线上。

题目分析

首先必然每一个点都可以作为一组解中的点。

不妨其中一个点编号为 \(1\)。找一个点作为第二个点，为了使没有点在这条边上，这个点与 \(1\) 号点的距离要是最短的。

接下来找第三个点，只需使这个点与前两个点构成的三角形面积最小就行了。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 5;
const double esp = 1e-8;
 
int n;
double x[N], y[N];
 
double dis(double ax, double ay, double bx, double by)
{
	return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
}
 
double area(double ax, double ay, double bx, double by, double cx, double cy)
{
	double tx1 = bx - ax, ty1 = by - ay, tx2 = cx - ax, ty2 = cy - ay;
	return fabs(tx1 * ty2 - tx2 * ty1) / 2;
}
 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%lf%lf", &x[i], &y[i]);
	
	int t = 2;
	double dt = dis(x[1], y[1], x[2], y[2]);
	for(int i = 3; i <= n; i ++ )
	{
		double d = dis(x[1], y[1], x[i], y[i]);
		if(d < dt)
		{
			dt = d;
			t = i;
		}
	}
	double ma = 1e20;
	int rt;
	for(int i = 2; i <= n; i ++ )
		if(i != t)
		{
			double xx = area(x[1], y[1], x[t], y[t], x[i], y[i]);
			if(xx > esp && xx <= ma)
			{
				rt = i;
				ma = xx;
			}
		}
	printf("%d %d %d\n", 1, t, rt);
	return 0;
}