Tävlingsprogrammering/Uppgifter/Samla stenar
Samla stenar
N stenar ligger stökigt utspridda i ett koordinatsystem. Varje sten har en koordinat (xi,yi). Det har blivit dags att samla ihop stenarna, och till din hjälp har du skaffat en supersmart stenplockarmaskin.
Innan maskinen startar så ska du välja en punkt som du kallar uppsamlingspunkten S. Det är punkten där maskinen börjar, och där den kommer att placera de insamlande stenarna. Den måste ligga någonstans på x-axeln. Maskinen börjar på uppsamlingspunkten (S,0), och samlar sedan upp alla stenar och placerar dem på uppsamlingspunkten. Maskinen kan bara bära en sten i taget.
Bränsle är dyrt, så du tänkte försöka vara lite smart. Du vet att när maskinen sätter igång så åker den alltid och samlar upp alla stenar på optimalt vis, men de är upp till dig att välja uppsamlingspunkten så att den totala sträckan maskinen åkt blir minimal. Hur lång blir denna sträcka, givet att du väljer uppsamlingspunkten optimalt? Du kan betrakta stenarna och maskinen som punkter i talplanet.
Delpoäng
På det här problemet kan du samla poäng trots att du inte löser problemet helt och hållet.
- För 30% av poängen gäller att alla stenar ligger på x-axeln, och 1≤N≤1000.
- För 30% av poängen gäller att alla stenar ligger på x-axeln, och 1≤N≤105.
- För 40% av poängen gäller att stenarna kan ligga var som helst inom angiven radie, och 1≤N≤105.
Indata
På första raden i indata står heltalet N, antalet stenar.
Sedan följer N rader med par av flyttal xiyi, stenarnas koordinater. Alla stenar i indata ligger maximalt 100 längdenheter från origo.
Utdata
Utdata ska bestå av ett enda flyttal: Minsta möjliga totala sträcka som maskinen har åkt efter att den samlat upp alla stenar. Ett fel mindre än 10−4 betraktas som korrekt.
Tips: Se till att ditt program skriver ut tillräckligt många decimaler även när svaret är stort.
Exempel
Körningsexempel 1
2 1 0 1.5 0 Svar: 1
Körningsexempel 2
2 3 2 1 2 Svar: 8.944271910
Körningsexempel 3
5 3.79732 0 6.87374 0 5.9189 0 2.56951 0 8.84052 0 Svar: 18.694860000
Körningsexempel 4
7 5.46618 9.46294 1.43546 1.58368 0.616149 6.18241 2.73059 9.56861 0.240727 3.9266 5.22356 8.6161 7.3643 6.98542 Svar: 99.854778111
Lösning[redigera]
Problemet handlar om att hitta den punkt på x-axeln S så att: summan av alla stenars avstånd till (S,0) är minimal. Låt oss beskriva hur vi kan lösa de två delproblemen.
Delpoäng (60p)[redigera]
Låt oss först beskriva hur man enkelt kan få 60 poäng på problemet. Givet i indataspecifikationen är att alla stenar ligger även de på x-axeln. Vi kallar det att problemet i detta fall är endimensionellt.
Låt oss börja med en insikt som gäller för det endimensionella fallet: Det är alltid optimalt att placera punkten ovanpå medianen. Om det finns två medianer (N är jämnt) så spelar det ingen roll vilken vi väljer. Vi undersöker här varför.
Antag att N är udda, och vi har valt att sätta uppsamlingspunkten ovanpå stenen i mitten. För valet av denna punkt har vi en viss totalsträcka som maskinen måste åka. Om vi då flyttar maskinen lite åt ena hållet så kommer avståndet till fler än hälften av punkterna att öka, samtidigt som avståndet till mindre än hälften av punkterna minskar med samma sträcka. Alltså är det optimalt att sätta maskinen på stenen i mitten.
Men vad händer i fallet då vi har två mittpunkter? Då spelar det ingen roll var mellan dessa, eller ovanpå vilken av dessa två punkter som vi sätter den. Använd resonemanget ovan och försök övertyga dig själv om att det är så, se det som en övning.
Att hitta medianen kan vi enkelt göra genom att sortera indata och välja den N/2:te punkten, avrundat neråt. Är N udda får vi punkten i mitten, är N jämnt får vi punkten till vänster i mitten. Observera dock: att prova alla punkter räcker bara till 30 poäng, det blir för långsamt då N är större än ungefär 10 000.
Full poäng[redigera]
För full poäng behöver vi ytterligare några insikter med oss innan vi är redo att skriva en lösning.
Kalla f(x) en funktion som beskriver summan av avståndet från (x,0) till alla punkter i indata. Största verktyget för att lösa problem är att funktionen f(x) är konvex (formad som ett U). Det innebär att den har precis ett minimum (eller ett sammanhängade minimalt område, se avsnittet ovan).
Hur vet vi att den är konvex? Börja med rita upp hur funktionen ser ut när den bara räknar ut avståndet till en sten. Det vi söker är alltså summan av ett antal sådana funktioner, och den summan är också konvex. Det kan man till exempel bevisa genom att använda derivator: för en konvex funktion gäller att andraderivatan f"(x) >= 0. Anta då att vi har två funktioner f(x), g(x) sådana att f"(x) > 0 och g"(x) > 0 (de är konvexa). Då behöver vi bara visa att (f(x) + g(x))" > 0, och det lämnas till läsaren som en övning.
Att hitta minimum i en konvex funktion (eller ekvivalent, maximum i en konkav funktion) är ett perfekt tillfälle att använda trinärsökning. Mer information om trinärsökning finns för den intresserade på http://en.wikipedia.org/wiki/Ternary_search. En mer effektiv variant av trinärsökning kallas gyllene snittet-sökning (Golden Section Search): http://en.wikipedia.org/wiki/Golden_section_search.
Lösning i C++ som använder sig av trinärsökning:
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const double eps = 1e-12;
double px[100005], py[100005];
int N;
double f(double x) {
double ret = 0;
for (int i = 0; i < N; ++i) {
double dx = px[i]-x;
double dy = py[i];
ret += sqrt(dx*dx + dy*dy);
}
return ret;
}
int main() {
cin >> N;
double l = 100.0, r = -100.0;
for (int i = 0; i < N; ++i) {
cin >> px[i] >> py[i];
l = min(l,px[i]);
r = max(r,px[i]);
}
while (l + eps < r) {
double lt = l+(r-l)/3;
double rt = l+2*(r-l)/3;
double f1 = f(lt);
double f2 = f(rt);
if (f1 > f2) {
l = lt;
} else {
r = rt;
}
}
printf("%.9lf\n",2*f((l+r)/2));
}
Lösning i Haskell som använder sig av gyllene snittet-sökning (av Anton Fors Hurdén):
import Control.Monad
φ = 0.61803398875
gss f a b c ε
| abs (fx - fb) < ε = fx + fb
| fx < fb = if c - b > b - a
then gss f b x c ε
else gss f a x b ε
| otherwise = if c - b > b - a
then gss f a b x ε
else gss f x b c ε
where
fx = f x
fb = f b
x = if c - b > b - a
then b + φ * (c - b)
else b + φ * (a - b)
parse [x, y] = return $ (read x, read y)
distance p o = sum $ map (\(x, y) -> sqrt ((x - o) * (x - o) + y * y)) p
main = do
n <- readLn
p <- replicateM n $ getLine >>= parse . words
print $ gss (distance p) (-100) 0 100 1e-8
Lösning i C som använder sig av gyllene snittet-sökning och som representerar punkterna som komplexa tal (av Anton Fors Hurdén):
#include <stdio.h>
#include <complex.h>
#define eps 0.00000001
#define phi 0.61803398875
#define abs(x) (((x) > 0) ? (x) : -(x))
double complex p[100000];
int n, i;
double f(double x) {
double sum = 0;
for (i = 0; i < n; i++) sum += cabs(p[i] - x);
return sum;
}
double gss(double a, double b, double c) {
double x = b + phi * ((c - b > b - a ? c : a) - b),
fx = f(x),
fb = f(b);
return abs(fx - fb) < eps
? fx + fb
: fx < fb
? c - b > b - a
? gss(b, x, c)
: gss(a, x, b)
: c - b > b - a
? gss(a, b, x)
: gss(x, b, c);
}
int main() {
double x, y, min = 100, max = -100;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%lf%lf", &x, &y);
if (x > max) max = x;
if (x < min) min = x;
p[i] = x + y * I;
}
printf("%.9lf\n", gss(min, (max + min) / 2, max));
}