JZOJ4033. 【GCJ2009B】Min Perimeter

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Description

給你一個整數座標的點集,詢問點集中最小的三角形周長是多少。退化的三角形也是允許的(面積為0)。

Input

第一行一個整數n表示共有n個點
接下來n行每行兩個整數xi,yi表示點的座標
保證沒有重複點

Output

僅一行包含一個實數表示最小的三角形周長,輸出和標準答案相差10^-9之內都被認為是正確的。

Sample Input

4
0 0
2 0
0 2
2 2

Sample Output

6.828427124746

Data Constraint

0 < n<=100000

題解

首先先看最最暴力的方法,O(n3)” role=”presentation” style=”position: relative;”>O(n3)O(n3)O(n^3)的暴力匹配。
很顯然這是不可行的。

而像這種題目一般就是用分治來做,
按照x從小到大排序,
每次選擇最中間,建點集分成大小相同的兩個部分。
現在就只需要考慮如何求出跨過中間線的三角形。
不過在此之前,就可以通過分治左右兩邊的點集得到一個最小值,
而通過這個最小值,對不少點進行剪枝。
假設當前的最小值為p,
你們肯能成為新的最小值的三個點只可能分佈在一個邊長為p,p/2的長方形中,
也就是說中線往左右各p/2裡面的所有點。
於是就先將這些點拿出來按照y排序,
然後用過佇列維護,
每次加入一個點,然後跟佇列裡面所有的點暴力配對。
最後再將一些不可能成為更新答案的點踢掉。

code

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 100003
#define M 103
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(ll &n)
{
n=0;
ch=G();
while((ch<'0' || ch>'9') && ch!='-')ch=G();
ll w=1;
if(ch=='-')w=-1,ch=G();
while('0'<=ch && ch<='9')n=(n<<3) (n<<1) ch-'0',ch=G();
n*=w;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10 '0');}
struct node
{
ll x,y;
}a[N],b[N];
db dis(node a,node b)
{
return sqrt((db)(a.x-b.x)*(a.x-b.x) (a.y-b.y)*(a.y-b.y));
}
db get(node a,node b,node c)
{
return dis(a,b) dis(a,c) dis(b,c);
}
bool cmp(node a,node b)
{
return a.x<b.x;
}
bool cmp1(node a,node b)
{
return a.y<b.y;
}
ll n;
db solve(int l,int r)
{
int m=(l r)>>1;
db mi=2147483647;
if(r-l<2)return mi;
mi=min(solve(l,m),solve(m 1,r));
db t=mi/2,w=a[m].x;
int st,fi;
for(st=m;st>=l && w-a[st].x<=t;st--);
for(fi=m;fi<=r && a[fi].x-w<=t;fi  );
for(int i=st 1;i<fi;i  )b[i-st]=a[i];
int p=fi-st-1;
sort(b 1,b 1 p,cmp1);
int id=1;
for(int i=1;i<=p;i  )
{
for(int j=id;j<i;j  )
for(int k=j 1;k<i;k  )
mi=min(mi,get(b[i],b[j],b[k]));
for(t=mi/2;b[i].y-b[id].y>t && id<i;id  );
}
return mi;  
}
int main()
{
read(n);
for(int i=1;i<=n;i  )
read(a[i].x),read(a[i].y);
sort(a 1,a 1 n,cmp);
printf("%.10lf",solve(1,n));
return 0;
}

相關文章

程式語言 最新文章