Euclidean Distance

Posted on | In , , ,

题目链接

题意

$n$维平面上有一个点，坐标是，现在想找一个点$P$，试他们的欧几里得距离最短。
要求$P$的坐标满足：
1.
2.

思路

拉格朗日乘数法

贪心

现在如果没有大于0的限制我们就已经解决了这道题，现在考虑一下，如何加上这样的限制。
我们可以贪心地把一部分正数填补到负数来，让原本负数取最值的点处于边界(0)，那么正数怎么来弥补呢。
经过观察可以发现，最好是正数均摊，这样产生的额外增加的比较少。想不明白可以自己画一下。
于是我们就有了这样的方案：

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 1e4 + 5;
 
inline ll gcd(ll a, ll b)
{
    if (a < b)
        swap(a, b);
    while (b)
    {
        ll t = a;
        a = b;
        b = t % b;
    }
    return a;
}
 
struct frac
{
    ll a, b;
    frac(ll a=0, ll b=1): a(a), b(b) {}
    inline bool operator < (const frac& x) const
    {
        return a * x.b < b * x.a;
    }
    inline bool operator > (const frac& x) const
    {
        return a * x.b > b * x.a;
    }
    inline bool operator == (const frac& x) const
    {
        return a == x.a && b == x.b;
    }
    inline bool operator >= (const frac& x) const
    {
        return *this > x || *this == x;
    }
    inline bool operator <= (const frac& x) const
    {
        return *this < x || *this == x;
    }
    inline void pretty()
    {
        ll g = gcd(abs(a), abs(b));
        if (g)
            a /= g, b /= g;
        if (a * b < 0)
            a = -abs(a), b = abs(b);
        else if (a < 0 && b < 0)
            a = abs(a), b = abs(b);
 
    }
    inline frac operator + (const frac& x) const
    {
        frac tmp = frac();
        tmp.a = a * x.b + x.a * b;
        tmp.b = b * x.b;
        tmp.pretty();
        return tmp;
    }
    inline frac operator - (const frac& x) const
    {
        frac tmp = frac();
        tmp.a = a * x.b - b * x.a;
        tmp.b = b * x.b;
        tmp.pretty();
        return tmp;
    }
    inline frac operator * (const frac& x) const
    {
        frac ret = frac();
        ret.a = a * x.a;
        ret.b = b * x.b;
        ret.pretty();
        return ret;
    }
    inline frac operator / (const frac& x) const
    {
        frac ret = frac();
        ret.a = a * x.b;
        ret.b = b * x.a;
        ret.pretty();
        return ret;
    }
    inline void print()
    {
        if (a == 0)
            printf("0\n");
        else if (b == 1)
            printf("%lld\n", a);
        else
            printf("%lld/%lld\n", a, b);
    }
};
frac a[N];
int main()
{
    int n, m;
    frac sum = frac(0, 1), one = frac(1, 1);
    while (~scanf("%d%d", &n, &m))
    {
        frac sum = frac(0, 1);
        for (int i = 1; i <= n; i++)
        {
            ll x;
            scanf("%lld", &x);
            a[i] = frac(x, m);
            sum = sum + a[i];
        }
        sort(a + 1, a + n + 1);
        frac remedy = frac(0, 1);
        frac c = (sum - one) / frac(n, 1);
        int p;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] >= c + remedy / frac(n - i + 1, 1))
            {
                p = i;
                break;
            }
            remedy = remedy - a[i] + c;
        }
		//dbg(remedy.a, remedy.b, c.a, c.b, p);
        frac ans = frac(0, 1);
        remedy = remedy / frac(n - p + 1, 1) + c;
        for (int i = 1; i < p && i <= n; i++)
        {
            ans = ans + a[i] * a[i];
          //  dbg(i, a[i].a, a[i].b, ans.a, ans.b);
        }
        ans = ans + remedy * remedy * frac(n - p + 1, 1);
        ans.print();
    }
    return 0;
}

顺便藏个分数模板。

0%