#include #include #define MAXN 1000000 struct bod { int x; int y; }; struct bod body[MAXN]; // Porovnávací funkce umístění bodů pro qsort int porovnej(const void* _a, const void* _b) { int* a = (int*) _a; int* b = (int*) _b; if (body[*a].y == body[*b].y) return body[*b].x - body[*a].x; return body[*b].y - body[*a].y; } // Funkce, která spočítá vektorový součin // Pracujeme s velkými čísly, tak nezapomeňme na používání long long int-ů long long int vek_soucin(struct bod a, struct bod b, struct bod t) { struct bod vek_b; vek_b.x = b.x - a.x; vek_b.y = b.y - a.y; struct bod vek_t; vek_t.x = t.x - a.x; vek_t.y = t.y - a.y; return (long long int) vek_b.x * (long long int) vek_t.y - (long long int) vek_b.y * (long long int) vek_t.x; } int main() { int i; int N; // Načteme vstup scanf("%d", &N); for (i = 0; i < N; ++i) scanf("%d%d", &(body[i].x), &(body[i].y)); int nejvyssi = 0; // Indexy nejvýše a nejníže položeného bodu int nejnizsi = 0; for (i = 1; i < N; ++i) { // Najdeme nejvýše a nejníže položené body if ((body[i].y > body[nejvyssi].y) || (body[i].y == body[nejvyssi].y && body[i].x > body[nejvyssi].x)) nejvyssi = i; if ((body[i].y < body[nejnizsi].y) || (body[i].y == body[nejnizsi].y && body[i].x < body[nejnizsi].x)) nejnizsi = i; } int levy[N], pravy[N]; // Pole s indexy bodů přiřazené do levé a pravé části int levyI, pravyI; // Koncové indexy příslušných polí deklarovaných na předchozím řádku levyI = pravyI = 0; for (i = 0; i < N; ++i) { // Rozdělíme body do levé a pravé části if (vek_soucin(body[nejvyssi], body[nejnizsi], body[i]) > 0) pravy[pravyI++] = i; else levy[levyI++] = i; } // Setřídíme části odshora dolů qsort(levy, levyI, sizeof(int), porovnej); qsort(pravy, pravyI, sizeof(int), porovnej); // Výpis výsledku for (i = 0; i < levyI; ++i) printf("%d ", levy[i]); for (i = pravyI-1; i >= 0; --i) // Druhou část chceme vypsat v opačném pořadí printf("%d ", pravy[i]); printf("\n"); return 0; }