YbtOJ 825「计算几何初探」三角查找
题目链接：YbtOJ #825
小 A 有一张二维平面，其中有 n 个点 (x_i,y_i)。
他想要知道，是否存在三个点 (x_A,y_A),(x_B,y_B),(x_C,y_C)，满足它们构成的三角形的面积 恰好 为 m。
若存在，请给出任意一组符合条件的三个点。
3le nle2times10^3，1le mle2times10^{18}，-10^9le x_i,y_ile 10^9，保证不存在三点共线。
Solution
暴力枚举每条连线作为三角形的底，然后只需要判断是否存在一个点到这条连线的距离恰好等于 frac{2m}{l} 。
将这条线段旋成直角坐标系的纵轴，若能让所有点横坐标有序，就可以直接二分。于是问题就变成了如何维护点的顺序。
发现若将所有点两两之间的连线按斜率排遍序，按照斜率从小到大枚举，则任意两点的横坐标大小关系只会变化恰好一次。
初始所有点按原横坐标大小顺序排序，枚举连线的过程中每次交换两端点，再在连线两边分别二分查找即可。
Code
代码语言：javascript复制#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("Yesn%d %dn%d %dn%d %dn",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;
}
