【枚举】【计算几何】Codeforces1019 D Large Triangle_综合

分析：

事先说明。。。。Codeforces强大的评测机。。。是可以支持n=2000时的 $O(n^3)$ 算法的。。
所以这题写 $O(n^2logn)$ 算法纯属练手。。。如果只是想过题的话，去写 $O(n^3)$ 更容易

首先，可以枚举三角形的一条边，因为三角形面积 $S=\frac 1 2\times d\times h$ ，所以现在已经知道了 $d$ ，无非就是求一个合适的 $h$ 。如果能够使得其他所有点，按照与这条线的距离排序，那么在排好序的点中，二分查找就可以了。

所以这题的重点就是：如何维护所有点按照与这条边的距离有序。

有一个巧妙的算法，先把所有的边枚举一下，按照斜率排序。按照斜率从小到大依次处理

假设当前所有点都满足对当前边有序，那么处理下一条边（斜率比它大）时，所有点中，只有当前这条边的两个端点的顺序有变化，其余的点顺序仍然是一致的。

证明应该很显然，对于任意一对关系：u，v，若u到当前边的距离比v大，但对下一条边u的距离又比v小，那么这两条边的斜率必然包含了(u,v)这个斜率，但是(u,v)这条边又必然存在（因为所有点对都被枚举了），所以当u,v顺序发生变化时，必然是以(u,v)这条边为界限。

所以就可以得到一个 $O(n^2logn)$ 的算法了

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 2010
using namespace std;
typedef long long ll;
ll s;
struct node{ll x,y;node () {}node (ll xx,ll yy):x(xx),y(yy) {}node operator -(const node &a) const {return node(x-a.x,y-a.y);   }node operator +(const node &a) const {return node(x+a.x,y+a.y);   }ll operator ^(const node &a) const {return x*a.y-y*a.x; }bool operator < (const node &a) const {return y==a.y?x<a.x:y<a.y;}
}p[MAXN];
struct Line{node p;int u,v;Line () {}Line (node p1,int u1,int v1):p(p1),u(u1),v(v1) {}bool operator < (const Line &a) const {return (p^a.p) < 0;}
}l1[MAXN*MAXN];
int pos[MAXN];
ll check(int x,int y,int z){return abs((p[y]-p[x])^(p[z]-p[x]));    
}
int main(){int n;SF("%d%I64d",&n,&s);s*=2ll;for(int i=1;i<=n;i++)SF("%I64d%I64d",&p[i].x,&p[i].y);   sort(p+1,p+1+n);int cnt=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)l1[++cnt]=Line(p[i]-p[j],i,j);sort(l1+1,l1+1+cnt);for(int i=1;i<=n;i++)pos[i]=i;for(int i=1;i<=cnt;i++){int u=pos[l1[i].u];int v=pos[l1[i].v];int l=1,r=u-1;while(l<=r){int mid=(l+r)>>1;ll s1=check(mid,u,v);if(s1==s){PF("Yes\n");PF("%I64d %I64d\n%I64d %I64d\n%I64d %I64d\n",p[u].x,p[u].y,p[v].x,p[v].y,p[mid].x,p[mid].y);return 0;}if(s1<s)l=mid+1;elser=mid-1;}l=v+1,r=n;while(l<=r){int mid=(l+r)>>1;ll s1=check(mid,u,v);if(s1==s){PF("Yes\n");PF("%I64d %I64d\n%I64d %I64d\n%I64d %I64d\n",p[u].x,p[u].y,p[v].x,p[v].y,p[mid].x,p[mid].y);return 0;}if(s1<s)l=mid+1;elser=mid-1;}swap(pos[l1[i].u],pos[l1[i].v]);swap(p[u],p[v]);}PF("No");
}