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

#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;
}