HDU 3548 Enumerate the Triangles（找周長最小的三角形+優化）

HDU 3548 Enumerate the Triangles（找周長最小的三角形+優化）

【題意】：平面上有n(n<=1000)點，問組成的三角形中，周長最小是多少。

【解題思路】：此題有個優化點，首先考慮直接枚舉的話，是O(n^3)肯定會超時，所以要優化。接著我們考慮，判斷組成三角形的條件和特殊情況，周長C=L1+L2+L3，有C> 2Li，假設Li的兩端分別為點a、b，則又有Li>=| Xa-Xb |，故C> 2*| Xa-Xb |。所以先按照X坐標從小到大排序，然後當已得到的最小值area<= 2*|Xa-Xb|的時候，就跳出循環。

代碼：

/*
* Problem: HDU No.3548
* Running time: 93MS
* Complier: G++
* Author: javaherongwei
* Create Time: 15:29 2015/10/4 星期日
*/
#include 
#include 
#include 
#include 
#include 
typedef long long LL;
using namespace std;

#define min(a,b) alen_cb&&len_ab+len_cb>len_ac&&len_ac+len_cb>len_ab) return true;
    return false;
}

inline LL read(){
    int  c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    return c*f;
}
int main()
{
    int t,tot=1;t=read();
    while(t--)
    {
        n=read();
        for(int i=0; i