Cod sursa(job #1325802)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 24 ianuarie 2015 13:06:23
Problema A+B Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.08 kb
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#define eps 1.e-7
using namespace std;

struct point {
    double x, y;
};

struct circle {
    point c;
    double r;
};


vector<point> P;
vector<point> C;

bool eq(point a, point b) {
  if(abs(a.x - b.x) <= eps && abs(a.y - b.y) <= eps)
     return 1;
  return 0;
}

double direction(point p1, point p2, point p3) {
  return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y);
}
// 0 -> col

double dist(point p1, point p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

double det(double a, double b, double c, double d, double e, double f) {
    return a * (d - f) + c * (f - b) + e * (b - d);
}

point center(point p1, point p2, point p3) {
    point ans;
    if(!det(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)) {
        return p1;
    }
    ans.x = det(p1.x * p1.x + p1.y * p1.y, p1.y,
                p2.x * p2.x + p2.y * p2.y, p2.y,
                p3.x * p3.x + p3.y * p3.y, p3.y) /
                (2 * det(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y));
    ans.y = det(p1.x, p1.x * p1.x + p1.y * p1.y,
                p2.x, p2.x * p2.x + p2.y * p2.y,
                p3.x, p3.x * p3.x + p3.y * p3.y) /
                (2 * det(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y));
    return ans;
}

point mid(point p1, point p2) {
    point ans;
    ans.x = (max(p1.x, p2.x) - min(p2.x, p1.x)) / 2;
    ans.y = (max(p1.y, p2.y) - min(p2.y, p1.y)) / 2;
    return ans;
}

circle make_circle2(point p1, point p2) {
    circle ans;
    ans.c = mid(p1, p2);
    ans.r = dist(p1, p2) / 2;
    return ans;
}

circle make_circle1(point p1, point p2, point p3) {
    circle ans;
    while((p1.x > p2.x) || (p1.x == p2.x && p1.y > p2.y))
        swap(p1, p2);
    if((p2.x > p3.x) || (p2.x == p3.x && p2.y > p3.y))
        swap(p2, p3);
    if(fabs(direction(p1, p2, p3)) <= eps)
        return make_circle2(p1, p3);
    ans.c = center(p1, p2, p3);
    ans.r = dist(ans.c, p1);
    return ans;
}

circle make_circle(int i, vector<point> C) {
    circle ans;
    if(i == 0) {
        point A;
        A.x = 0;
        A.y = 0;
        ans.c = A;
        ans.r = -1;
        return ans;
    }
    if(i == 1) {
        ans.c = C[0];
        ans.r = 0;
        return ans;
    }
    if(i == 2) {
        return make_circle2(C[0], C[1]);
    }
    return make_circle1(C[0], C[1], C[2]);
}

circle MEC(const vector<point> &P, const int &i1, vector<point> &C, const int &i2) {
    cout << i1 << ' ' << i2 << '\n';
    if(i1 == 0 || i2 >= 3) {
        return make_circle(i2, C);
    }
    /*if(i2 == 3) {
        return make_circle1(C[0], C[1], C[2]);
    }
    else if(i1 + i2 == 3) {
        while(i1 > 0)
            C.push_back(P[--i1]);
        return make_circle1(C[0], C[1], C[2]);
    }
    else if(i1 + i2 == 2) {
        while(i1 > 0)
            C.push_back(P[--i1]);
        return make_circle2(C[0], C[1]);
    }
    else if(i1 + i2 == 1) {
        if(i1 > 0)
            C.push_back(P[0]);
        return make_circle(i2 + 1);
    }*/
    else {
        point p = P[i1 - 1];
        circle circ = MEC(P, i1 - 1, C, i2);
        if(circ.r == -1 || dist(P[i1 - 1], circ.c) > circ.r) {
            cout << P[i1 - 1].x << ' ' << P[i1 - 1].y << '\n';
            point A = circ.c;
            cout << A.x << ' ' << A.y << ' ' << circ.r << '\n';
            C[i2] = p;
            circ = MEC(P, i1 - 1, C, i2 + 1);
        }
        return circ;
    }
}

int N;

int main()
{
    ifstream cin("test.in");
    cin >> N;
    cout << fixed << setprecision(2);
    while(N) {
        P.clear();
        C.clear();
        point cur;
        circle ans;
        for(int i = 1; i <= N; ++i) {
            cin >> cur.x >> cur.y;
            P.push_back(cur);
        }
        //ans = make_circle1(P[0], P[1], P[2]);
        ans = MEC(P, P.size(), C, 0);
        point ans2 = ans.c;
        cout << ans2.x << ' ' << ans2.y << ' ' << ans.r << '\n';
        cin >> N;
    }
    return 0;
}