C. Recycling Bottles （几何）

• 题目链接：http://codeforces.com/contest/672/problem/C
• 题意：有两个人，a 和 b ，一个垃圾桶 t，给你他们在二维平面的坐标，和n个空瓶子的坐标，a和b要把这些垃圾放进垃圾桶。保证所有坐标不重合，问a和b总的最小行走距离。
• 算法：几何
• 思路：分为三种情况
  
  • a和b一定都参与——disl
  • 只有a参与————disa
  • 只有b参与————disb

---

#include <bits/stdc++.h>
#define pi acos(-1.0 )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL , LL>  PLL;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;//4e18 ~= 2^62
const int maxn =1e5 + 10;
const LL mod = 998244353;

PLL a, b, t, c[maxn];
double dis(PLL a, PLL b)
{
    return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}

int main()
{
    scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &a.first, &a.second, &b.first, &b.second, &t.first, &t.second);
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%I64d%I64d", &c[i].first, &c[i].second);
    double l = dis(c[1], t);
    double disa = dis(a, c[1]) + l;
    double disb = dis(b, c[1]) + l;
    double disl = min(disa, disb);
    double sum = 2*l;
    for(int i=2; i<=n; i++){
        l = dis(c[i], t);
        disl = min(min(disl+2*l, disa+dis(b, c[i])+l), disb+dis(a, c[i])+l);
        disa = min(disa+2*l, sum+dis(a, c[i])+l);
        disb = min(disb+2*l, sum+dis(b, c[i])+l);
        sum+=2*l;
    }
    cout << fixed << setprecision(15) << min(min(disl,disa), disb) << endl;
}