|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
Sponzori
|
|
|
zadatak: Flojd
|
Ko je ona tvrda glava, što do podne uvek spava? Ko je dasa u ekstazi, kada preko stotke
gazi? Naravno, to je Flojd. Flojd je mudar, hrabar i ludo vozi. Međutim, čak i takvom
reli asu je ponekad potrebna pomoć.
Organizatori predstojeće reli trke su odlučili da uvedu nova pravila. Na stazu su
postavili N zastavica numerisanih brojevima od 1 do N, tako da i-ta
zastavica ima koordinate (Xi, Yi). Kao i svaki pravi reli,
i ovaj naš se odvija na neuređenom, zemljanom terenu, na kome se tragovi točkova savršeno vide.
Pravila trke su sledeća: vozač treba da izabere redosled zastavica z1, ..., zN,
i potom pravolinijski ide od zastavice numerisane brojem z1 do z2,
od z2 do z3, i tako sve dok ne stigne do zastavice zN.
Naravno, kako bi se umešnost vozača što više stavila na ispit, postoje i dodatna pravila koja donose dodatne
poene. Naime, iz početne zastavice vozač sme da ide samo severno, odnosno ka zastavici
koja ima veću y koordinatu. Potom sme da ide samo južno, odnosno ka zastavici koja ima
manju y koordinatu, i tako dalje. Drugim reqima, treba da važi yz1 <
yz2 > yz3 < yz4 > ....
Takođe, nije dozvoljeno da trag koji točkovi ostavljaju ima samopresecanja, osim u tačkama
na kojima se nalaze zastavice, i naravno, potrebno je obići svaku zastavicu tačno jednom.
Pomozite Flojdu da nađe takvu putanju i time osvoji sve moguće poene i srca publike!
Ulaz.
(Ulazni podaci se učitavaju iz datoteke flojd.in.)
U ulaznoj datoteci se u prvom redu nalazi broj N (1 ≤ N ≤ 5000), broj zastavica.
U sledećih N redova se nalaze po dva cela broja iz intervala [1, 107], pri
čemu i-ti red sadrži (xi, yi), koordinate i-te zastavice.
Nikoje tri tačke nisu kolinearne i ne postoje dve tačke sa istom y koordinatom.
Izlaz.
(Izlazni podaci se ispisuju u datoteku flojd.out)
Ukoliko postoji putanja koja zadovoljava kriterijume, ispisati redne brojeve zastavice u redosledu
u kojem ih treba obići, po jednu u svakom redu. Ukoliko postoji više mogućih putanja, štampati bilo koju.
Ukoliko takva putanja ne postoji, ispisati -1.
Primer 1.
flojd.in
|
|
flojd.out
|
3
1 1
5 5
2 3
|
|
1
2
3
|
Napomena.
U 75% test primera ima najviše 3000 zastavica.
|
|
fajl: flojd.cpp
|
#include <iostream>
#include <cstdio>
using namespace std;
const char inFileName[] = "flojd.in";
const char outFileName[] = "flojd.out";
const int MaxN = 5001;
int n;
long x[MaxN], y[MaxN];
int next[MaxN], prev[MaxN];
bool used[MaxN];
bool right(int a, int b, int c) {
long long A = y[b] - y[a], B = x[a] - x[b], C = A * x[a] + B * y[a];
return A * x[c] + B * y[c] - C > 0;
}
int find_right(int a) {
int r = -1;
for (int i = 0; i < n; i++) {
if (i == a || used[i]) continue;
else {
if (r == -1) r = i;
else if (right(a, r, i)) r = i;
}
}
return r;
}
int convex_hull() {
long ysmall = y[0];
int ind = 0;
for (int i = 1; i < n; i++) {
if (y[i] < ysmall) {
ysmall = y[i];
ind = i;
}
}
int start = ind;
next[ind] = ind;
prev[ind] = ind;
bool done = false;
while (!done) {
int nextInd = find_right(ind);
prev[nextInd] = ind;
next[ind] = nextInd;
ind = nextInd;
if (nextInd == start)
done = true;
}
return start;
}
void delete_point(int p) {
int s = prev[p], q = next[p];
while (s != q) {
int nextS = find_right(s);
next[s] = nextS;
prev[nextS] = s;
s = nextS;
}
}
int main() {
freopen(inFileName, "r", stdin);
freopen(outFileName, "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%ld %ld", &x[i], &y[i]);
used[i] = false;
}
int currentPoint = convex_hull();
bool pickHigher = true;
for (int i = 0; i < n - 3; i++) {
printf("%d\n", currentPoint+1);
int c1 = prev[currentPoint], c2 = next[currentPoint];
used[currentPoint] = true;
delete_point(currentPoint);
if (pickHigher) {
if (y[c1] > y[c2]) currentPoint = c1;
else currentPoint = c2;
} else {
if (y[c1] < y[c2]) currentPoint = c1;
else currentPoint = c2;
}
pickHigher = !pickHigher;
}
int c1 = prev[currentPoint], c2 = next[currentPoint];
if (pickHigher) {
if (y[c1] < y[c2]) swap(c1, c2);
} else {
if (y[c1] > y[c2]) swap(c1, c2);
}
printf("%d\n%d\n%d\n", currentPoint+1, c1+1, c2+1);
return 0;
}
|
|
|