competitive-programming/solved-uva/11612.cpp at master · the-redback/competitive-programming · GitHub

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
/**
 *                                   ____
 *       ____ ___  ____ ________  __/ __/
 *      / __ `__ \/ __ `/ ___/ / / / /_
 *     / / / / / / /_/ / /  / /_/ / __/
 *    /_/ /_/ /_/\__,_/_/   \__,_/_/
 *
 *    @link : https://the-redback.com
 */

#include <bits/stdc++.h>
using namespace std;

#define mem(a, b) memset(a, b, sizeof(a))
#define pb        push_back
#define pp        pop_back
#define inf       10e9  // 10^9
#define meminf    100
#define eps       10e-9
#define NN        1000000
struct P {
    double x, y;
    int ii;
    P(double X, double Y, int i) {
        x = X;
        y = Y;
        ii = i;
    }
    P(double X, double Y) {
        x = X;
        y = Y;
    }
};

vector<P> v;

P MV(P a, P b) { return P(b.x - a.x, b.y - a.y); }

double DP(P a, P b) { return a.x * b.x + a.y * b.y; }

double CP(P a, P b) { return a.x * b.y - a.y * b.x; }

double A(P a) { return sqrt(a.x * a.x + a.y * a.y); }

P ADD(P a, P b) { return P(a.x + b.x, a.y + b.y); }

P LV(P a, double l) { return P(a.x * l / A(a), a.y * l / A(a)); }

P pvt(0, 0);

bool comp(P a, P b)  // False hoile sort korbe
{
    int c = CP(MV(pvt, a), MV(pvt, b));
    if (c) return c > 0;
    return A(MV(pvt, a)) < A(MV(pvt, b));
}

void checkPvt(void) {
    pvt.x = inf;
    pvt.y = inf;
    for (int i = 0; i < v.size(); i++) {
        if (pvt.y > v[i].y)
            pvt = v[i];
        else if (pvt.y == v[i].y && pvt.x > v[i].x)
            pvt = v[i];
    }
}

vector<P> q;

int checkline(void) {
    int n = v.size();
    if (CP(MV(v[0], v[1]), MV(v[0], v[n - 1])) == 0) return 1;
    return 0;
}

void go(void) {
    q.clear();
    int n = v.size();
    q.pb(v[n - 1]);
    v.pp();
    for (int i = v.size() - 1; i >= 0; i--) {
        if (CP(MV(v[0], q[q.size() - 1]), MV(v[0], v[i])) == 0) {
            q.pb(v[i]);
            v.pp();
        } else
            break;
    }
    for (int i = 0; i < q.size(); i++) v.pb(q[i]);
}

int main() {
    ios_base::sync_with_stdio(false);
    int t = 1, tc;
    int i, j, k, l, m, n;
    double x, y, z, u, w, xx, yy, zz, d;
    double aa, bb, cc, dd;
    // cin>>tc;
    while (cin >> n) {
        if (!n) return 0;
        v.clear();
        for (i = 0; i < n; i++) {
            cin >> k >> l;
            v.pb(P(k, l, i));
        }
        checkPvt();
        sort(v.begin(), v.end(), comp);
        if (checkline()) {
            puts("no solution");
            continue;
        }
        go();
        int fl = 0, ix = inf;
        for (i = 0; i <= v.size() && i != ix; i++) {
            if (i == v.size()) {
                i %= v.size();
                i--;
            } else if (fl) {
                printf("%d ", v[i].ii);
            } else if (v[i].ii == 0) {
                printf("%d ", v[i].ii);
                fl = 1;
                ix = i;
            }
        }
        printf("0\n");
    }
    return 0;
}