2019-08-30 19:53:15

### 找到一个在 $AB$ 的左下方且离 $AB$ 最远的点

$$\scriptsize\color{gray}{\text{图片来自 hyj 的 blog}}$$

\begin{aligned}\vec{AB}\times\vec{AC}&=(x_B-x_A)(y_C-y_A)-(x_C-x_A)(y_B-y_A)\\&=(x_B-x_A)y_C-(x_B-x_A)y_A-(y_B-y_A)x_C+(y_B-y_A)x_A\\&=(x_B-x_A)y_C+(y_A-y_B)x_C-(x_B-x_A)y_A+(y_B-y_A)x_A\end{aligned}

### 递归处理 $AC$ 与 $BC$

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

int X=0,w=1; char a=getchar();
while (a<'0'||a>'9') { if (a=='-') w=-1; a=getchar(); }
while (a>='0'&&a<='9') X=X*10+a-'0',a=getchar();
return X*w;
}

const int N=200+10;
const int M=10000+10;
const int inf=0x3f3f3f3f;

struct UFS { //并查集
int f[N];
inline void init(int n) { for (re int i=1;i<=n;++i) f[i]=i; }
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
inline void merge(int x,int y) { x=find(x),y=find(y); if (x!=y) f[x]=y; }
inline int check(int x,int y) { return find(x)==find(y); }
};

struct Edge { int u,v,w,a,b; };
inline int cmp(Edge a,Edge b) { return a.w<b.w; }

//计算几何相关
struct Point { int x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n,m;
UFS S;
Point ans=(Point){inf,inf};
Edge e[M];

//Kruskal，返回找到的点
inline Point Kruskal() {
Point res=(Point){0,0}; int tot=0;
sort(e+1,e+m+1,cmp); S.init(n);
for (re int i=1;i<=m;++i) {
int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b;
if (S.check(u,v)) continue;
S.merge(u,v),res.x+=a,res.y+=b,++tot;
if (tot==n-1) break;
}
/*更新答案*/
ll Ans=1ll*ans.x*ans.y,now=1ll*res.x*res.y;
if (Ans>now||(Ans==now&&ans.x>res.x)) ans=res;
return res;
}

//递归处理
inline void solve(Point A,Point B) {
for (re int i=1;i<=m;++i) e[i].w=e[i].b*(B.x-A.x)+e[i].a*(A.y-B.y);
Point C=Kruskal();
if (cross(B-A,C-A)>=0) return; //边界
solve(A,C),solve(C,B);
}

int main() {
}