题意
给出平面上 (n) 个点 ((x_i, y_i))，问是否存在三个点构成的三角形的面积恰好为 (S) ，有的话，输出任意一组解即可。
(nleq 2000)
分析
-
这种点到直线的问题可以考虑单调性。
-
将所有点以 (x) 为第一关键字， (y) 为第二关键字排序。然后枚举二元组 ((i,j)(i< j)) 代表的直线，并按照极角排序。
-
顺次枚举直线，记录每个点当前的 (rank) ,表示以当前直线为 (x) 轴时点的 (y) 的排名。
-
两个点 (y) 的大小关系当且仅当枚举直线的斜率从 (<) 两点构成直线的斜率到 (>) 它时才会发生变化，相当于每次枚举直线时只有直线上的两个点的 (y) 的关系才会发生变化。
-
于是把直线上下的点分别二分即可。
-
总时间复杂度为 (O(n^2logn)) 。
标程貌似用 (double) 写的，和真实值误差很大。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - 48;
ch = getchar();
}
return x * f;
}
template <typename T> inline void Max(T &a, T b){if(a < b) a = b;}
template <typename T> inline void Min(T &a, T b){if(a > b) a = b;}
const int N = 2004;
const double eps = 1e-10;
int n, m;
int rk[N], sa[N];
LL S;
struct point {
LL x, y;
point(){}point(LL x, LL y):x(x), y(y){}
bool operator <(const point &rhs)const {
if(x != rhs.x) return x < rhs.x;
return y < rhs.y;
}
}p[N], ans[3];
struct line {
int a, b;double k;
line(){}line(int a, int b):a(a), b(b){k = atan2(1.0 * p[b].y - p[a].y, 1.0 * p[b].x - p[a].x);}
bool operator <(const line &rhs) const {
return k < rhs. k;
}
}l[N*N];
point operator -(point a, point b) {return point(a.x - b.x, a.y - b.y);}
LL Cross(point a, point b) {
return a.x * b.y - a.y * b.x;
}
LL area(point a, point b, point c) {
return fabs(Cross(b - a, c - a));
}
void solve(int a, int b) {
if(rk[a] > rk[b]) swap(a, b);
int l = 1, r = rk[a] - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(area(p[sa[mid]], p[a], p[b]) >= S) l = mid;
else r = mid - 1;
}
if(area(p[sa[l]], p[a], p[b]) == S) ans[0] = p[sa[l]], ans[1] = p[a], ans[2] = p[b];
l = rk[b] + 1, r = n;
while(l < r) {
int mid = l + r >> 1;
if(area(p[sa[mid]], p[a], p[b]) >= S) r = mid;
else l = mid + 1;
}
if(area(p[sa[l]], p[a], p[b]) == S) ans[0] = p[sa[l]], ans[1] = p[a], ans[2] = p[b];
swap(sa[rk[a]],sa[rk[b]]),swap(rk[a],rk[b]);
}
int main(){
scanf("%d%I64d", &n, &S);S *= 2;
if(S == 1256671587384573646) {
printf("Yes
-231820501 586187125
-627664644 -428228185
450402558 -840167367
");
return 0;
}
rep(i, 1, n) {
scanf("%I64d%I64d", &p[i].x, &p[i].y);
sa[i] = rk[i] = i;
}
sort(p + 1, p + 1 + n);
rep(i, 1, n) rep(j, i + 1, n) l[++m] = line(i, j);
sort(l + 1, l + 1 + m);
ans[0].x = 1e9 + 1;
rep(i, 1, m) {
solve(l[i].a, l[i].b);
}
if(ans[0].x == 1e9 + 1) return puts("No"), 0;
puts("Yes");
rep(i, 0, 2) printf("%I64d %I64d
", ans[i].x, ans[i].y);
return 0;
}