Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1551 Solved: 549[][][]
Description
Xaviera现在遇到了一个有趣的问题。平面上有N个点,Xaviera想找出周长最小的三角形。由于点非常多,分布也非常乱,所以Xaviera想请你来解决这个问题。为了减小问题的难度,这里的三角形也包括共线的三点。
Input
第一行包含一个整数N表示点的个数。接下来N行每行有两个整数,表示这个点的坐标。
Output
输出只有一行,包含一个6位小数,为周长最短的三角形的周长(四舍五入)。
Sample Input
41 12 33 33 4
Sample Output
3.414214
HINT
100%的数据中N≤200000。
Source
Day1
题解:
①cdq分治:对点的x坐标排序,然后进行分治,同时分治完了还需要求两边的互相影响。
一、在左边取两个点,右边一个。二、在右边取两个点,左边一个。
②再对分治左右两边的点再分别按照y值排序,
③剪枝:因为已经出来了一个比较优的ans,所以当一个点距离两边中界过远,那么我们就把它扔掉再不用管了。还有就是两边的点,y坐标距离过大的也不能进行选择,所以又进行一次剪枝。
④把上述东西串起来的是暴力枚举。
#include#include #define eps 1e-9#include #include #define go(i,a,b) for(int i=a;i<=b;i++)#define ro(i,a,b) for(int i=a;i>=b;i--)using namespace std;const int N=200010;struct P{double x,y;bool operator<(const P &a)const{return y >1,top=0,tp1=l,tp2=mid+1,Mid=s[mid].x; if(r-l+1<=3){sort(s+l,s+r+1);if(r-l+1==3)ans=min(ans,Cal(s[l],s[l+1],s[r]));return;} solve(l,mid);solve(mid+1,r); go(i,l,r)if((s[tp1] r)&&tp1<=mid)tmp[i]=s[tp1++];else tmp[i]=s[tp2++]; memcpy(s+l,tmp+l,sizeof(P)*(r-l+1)); go(i,l,r)if(abs(s[i].x-Mid)=ans/2)break; ro(k,j-1,1)ans=min(ans,Cal(newq[i],newq[j],newq[k])); }}int main(){ scanf("%d",&n);go(i,1,n) scanf("%lf%lf",&s[i].x,&s[i].y); sort(s+1,s+n+1,cmp); solve(1,n);printf("%.6f\n",ans);}//Paul_Guderian
燃烧的河流推倒了祈祷者的灯塔,
告诫的引擎怒吼着圣洁的墓志铭。——————汪峰《贫瘠之歌》