algorithms/acmp/0662.cpp at master · crystarm/algorithms · 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
// https://acmp.ru/index.asp?main=task&id_task=662
// computational geometry + sweep line

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

typedef string str;
typedef vector<double> vd;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i,a,b) for (int i = (a); i < (b); ++i)
#define rsr(v,n) (v).reserve(n)
#define pb push_back


static const double EPS = 1e-9;

struct pl { int a, b, c; };

static inline double sc(const pl& p, double x) { return (double)p.a * x * x + (double)p.b * x + (double)p.c; }

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    vector<pl> v(n);
    rep(i, 0, n) cin >> v[i].a >> v[i].b >> v[i].c;

    vd crit;
    rsr(crit, n * n + 2);
    crit.pb(1.0);

    rep(i, 0, n)
    {
        rep(j, i + 1, n)
        {
            double A = (double)v[i].a - (double)v[j].a;
            double B = (double)v[i].b - (double)v[j].b;
            double C = (double)v[i].c - (double)v[j].c;

            if (fabs(A) < EPS)
            {
                if (fabs(B) > EPS)
                {
                    double x = -C / B;
                    if (x > EPS && x <= 1.0 + EPS) crit.pb(x);
                }
            }
            else
            {
                double D = B * B - 4.0 * A * C;
                if (D > -EPS)
                {
                    if (D < 0) D = 0;
                    double r = sqrt(D);
                    double x1 = (-B - r) / (2.0 * A);
                    double x2 = (-B + r) / (2.0 * A);

                    if (x1 > EPS && x1 <= 1.0 + EPS) crit.pb(x1);
                    if (x2 > EPS && x2 <= 1.0 + EPS) crit.pb(x2);
                }
            }
        }
    }

    sort(all(crit));

    vector<str> out;
    vd scr(n);

    auto chk = [&](double x)
    {
        if (x <= 0 || x > 1.0 + EPS) return;

        rep(i, 0, n) scr[i] = sc(v[i], x);

        str r(n, '\0');
        rep(i, 0, n)
        {
            int bt = 0;
            rep(j, 0, n) if (scr[j] > scr[i] + EPS) ++bt;
            r[i] = (char)(bt + 1);
        }
        out.pb(r);
    };

    double prv = 0.0;
    double last = -1.0;

    for (double p : crit)
    {
        if (fabs(p - last) < EPS) continue;

        if (p > prv + EPS)
        {
            double mid = (prv + p) * 0.5;
            chk(mid);
        }

        chk(p);

        prv = p;
        last = p;
    }

    sort(all(out));
    out.erase(unique(all(out)), out.end());

    cout << sz(out) << '\n';
    return 0;
}