YbtOJ 825「计算几何初探」三角查找

(Updated: )
oi
,

题目链接：YbtOJ #825

小 A 有一张二维平面，其中有 $n$ 个点 $(x_i,y_i)$。

他想要知道，是否存在三个点 $(x_A,y_A),(x_B,y_B),(x_C,y_C)$，满足它们构成的三角形的面积 恰好 为 $m$。

若存在，请给出任意一组符合条件的三个点。

$3\le n\le2\times10^3$，$1\le m\le2\times10^{18}$，$-10^9\le x_i,y_i\le 10^9$，保证不存在三点共线。

Solution

暴力枚举每条连线作为三角形的底，然后只需要判断是否存在一个点到这条连线的距离恰好等于 $\frac{2m}{l}$ 。

将这条线段旋成直角坐标系的纵轴，若能让所有点横坐标有序，就可以直接二分。于是问题就变成了如何维护点的顺序。

发现若将所有点两两之间的连线按斜率排遍序，按照斜率从小到大枚举，则任意两点的横坐标大小关系只会变化恰好一次。

初始所有点按原横坐标大小顺序排序，枚举连线的过程中每次交换两端点，再在连线两边分别二分查找即可。

Code

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
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define int long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
Cn int N=2e3+10;
int n,m,cnt,id[N],r[N];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
PA a[N];
struct Line{int u,v;PA d;}l[N*N];
I bool operator < (Cn Line& x,Cn Line& y){return x.d.fi*y.d.se-x.d.se*y.d.fi>0;}
I void G(RI tl,RI tr,Line u){
    auto S=[&](PA p)->int{return abs(p.fi*u.d.se-p.se*u.d.fi);};
    RI mid;W(tl<=tr) mid=tl+tr>>1,S(MP(a[id[mid]].fi-a[u.u].fi,a[id[mid]].se-a[u.u].se))==m&&(printf("Yes\n%d %d\n%d %d\n%d %d\n",a[u.u].fi,a[u.u].se,a[u.v].fi,a[u.v].se,a[id[mid]].fi,a[id[mid]].se),exit(0),0),S(MP(a[id[mid]].fi-a[u.u].fi,a[id[mid]].se-a[u.u].se))<m?tr=mid-1:tl=mid+1;
}
signed main(){
    freopen("triangle.in","r",stdin),freopen("triangle.out","w",stdout);
    RI i,j;for(read(n,m),m*=2,i=1;i<=n;i++) read(a[i].fi,a[i].se);for(sort(a+1,a+n+1),i=1;i<=n;i++) for(id[r[i]=i]=i,j=1;j<i;j++) l[++cnt]=(Line){i,j,MP(a[i].fi-a[j].fi,a[i].se-a[j].se)};
    for(sort(l+1,l+cnt+1),i=1;i<=cnt;i++) r[l[i].u]>r[l[i].v]&&(swap(l[i].u,l[i].v),0),G(1,r[l[i].u]-1,l[i]),swap(r[l[i].u],r[l[i].v]),swap(id[r[l[i].u]],id[r[l[i].v]]);
    return puts("No"),0;
}