题目大意
给定 100000 个点,找到一个内部不包含其它的点的三角形,点不重合,不共线
做法
将点按\(x\)和\(y\)排序,从左到右扫描,找到的连续的面积非空的三角形即是答案
代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<long long, long long> pll;
typedef pair<pll, int> pii;
int n;
vector<pii> nds;
pll vec(pll a, pll b) {
return pll(b.x - a.x, b.y - a.y);
}
long long sze(const pll a, const pll b) {
return a.x * b.y - a.y * b.x;
}
int main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
double tx, ty;
cin >> tx >> ty;
nds.push_back(make_pair(make_pair(tx, ty), i + 1));
}
sort(nds.begin(), nds.end());
for (int i = 2; i < n; i++)
if (sze(vec(nds[i - 1].x, nds[i - 2].x),
vec(nds[i - 1].x, nds[i].x)) != 0) {
cout << nds[i - 2].y << ' '
<< nds[i - 1].y << ' '
<< nds[i].y << endl;
break;
}
return 0;
}