Cod sursa(job #2916555)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 30 iulie 2022 14:53:57
Problema Robot Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.61 kb
/// Preset de infoarena
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <iostream>

using namespace std;
#define int long long

ifstream fin("robot.in");
ofstream fout("robot.out");

const int inf = 1e9;
const double eps = 1e-6;
struct point {
    int x, y;
    bool operator < (const point &other) const {
        if(x == other.x)
            return (y < other.y);
        return (x < other.x);
    }
    bool operator == (const point &other) const {
        return ((x == other.x) && (y == other.y));
    }
};
struct heapNode {
    int nod;
    double cost;
    bool operator < (const heapNode &other) const {
        return cost > other.cost;
    }
};
point robot[12], obs[27][527], pct[1025];
double d[1025];
int n, m, lat[27], total_pct;
bool used[1025];
vector <heapNode> G[1025];
priority_queue <heapNode> heap;

int arie(point a, point b, point c)
{
    /// ax ay 1 )
    /// bx by 1  ) => A = ax * by + bx * cy + cx * ay - ax * cy - bx * ay - cx * by
    /// cx cy 1 )
    return a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.y * b.x - a.x * c.y;
}
point aux[1100005];
void get_obstacol(point v[], int &nr_lat)
{
    int ind = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= nr_lat; j++)
        {
            ind++;
            aux[ind].x = pct[1].x + v[j].x - robot[i].x;
            aux[ind].y = pct[1].y + v[j].y - robot[i].y;
        }
    }
    sort(aux + 1, aux + ind + 1);
    int j = 0;
    v[++j] = aux[1];
    for(int i = 2; i <= ind; i++)
    {
        if(arie(aux[1], aux[i], aux[ind]) >= 0)
        {
            while(j > 1 && arie(v[j - 1], v[j], aux[i]) <= 0)
                j--;
            v[++j] = aux[i];
        }
    }
    for(int i = ind - 1; i > 1; i--)
    {
        if(arie(aux[1], aux[i], aux[ind]) < 0)
        {
            while(j > 1 && arie(v[j - 1], v[j], aux[i]) <= 0)
                j--;
            v[++j] = aux[i];
        }
    }
    while(j > 1 && arie(v[j - 1], v[j], aux[1]) <= 0)
        j--;
    nr_lat = j;
}

double get_dist(point a, point b)
{
    double deltax = a.x - b.x, deltay = a.y - b.y;
    return sqrt(deltax * deltax + deltay * deltay);
}

bool coliniare(point a, point b, point x)
{
    return (fabs(get_dist(a, b) - get_dist(a, x) - get_dist(x, b)) < eps);
}

int modul(int x)
{
    if(x < 0)
        x = -x;
    return x;
}

bool intersectie(point a, point b, point x, point y)
{
    if(a == x || a == y || b == x || b == y)
        return 0;
    if(max(min(a.x, b.x), min(x.x, y.x)) > min(max(a.x, b.x), max(x.x, y.x)))
        return 0;
    if(max(min(a.y, b.y), min(x.y, y.y)) > min(max(a.y, b.y), max(x.y, y.y)))
        return 0;
    int a1 = arie(a, b, x), a2 = arie(a, b, y), a3 = arie(x, y, a), a4 = arie(x, y, b);
    return ((((a1 < 0) && (a2 > 0)) || ((a1 > 0) && (a2 < 0)))  &&  (((a3 < 0) && (a4 > 0)) || ((a3 > 0) && (a4 < 0))));
}

bool IsInside(point x, point v[], int vf)
{
    for(int i = 1; i <= vf; i++)
        if(x.x == v[i].x && x.y == v[i].y)
            return 0;
    for(int i = 1; i < vf; i++)
        if(coliniare(v[i], v[i + 1], x))
            return 0;
    if(coliniare(v[n], v[1], x))
        return 0;
    int a1 = 0, a2 = modul(arie(v[1], v[n], x));
    for(int i = 1; i < n; i++)
        a2 += modul(arie(v[i], v[i + 1], x));
    for(int i = 2; i < n; i++)
        a1 += modul(arie(v[i], v[i + 1], v[1]));
    return (a1 == a2);
}

bool valid(point a, point b)
{
    for(int i = 1; i <= m; i++)
    {
        if(IsInside(a, obs[i], lat[i]))
            return 0;
        if(IsInside(b, obs[i], lat[i]))
            return 0;
        for(int j = 1; j <= lat[i]; j++)
            for(int k = j + 1; k <= lat[i]; k++)
                if(intersectie(a, b, obs[i][j], obs[i][k]))
                    return 0;
    }
    return 1;
}

void dijkstra()
{
    for(int i = 2; i <= total_pct; i++)
        d[i] = inf;
    heap.push({1, 0});
    while(!heap.empty())
    {
        heapNode curr = heap.top();
        heap.pop();
        if(used[curr.nod])
            continue;
        used[curr.nod] = 1;
        for(heapNode nxt : G[curr.nod])
        {
            if(d[curr.nod] + nxt.cost - d[nxt.nod] < -eps)
            {
                d[nxt.nod] = d[curr.nod] + nxt.cost;
                heap.push({nxt.nod, d[nxt.nod]});
            }
        }
    }
}

signed main()
{
    fin >> n;
    pct[1] = {inf, inf};
    for(int i = 1; i <= n; i++)
    {
        fin >> robot[i].x >> robot[i].y;
        pct[1].x = min(pct[1].x, robot[i].x);
        pct[1].y = min(pct[1].y, robot[i].y);
    }
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> lat[i];
        for(int j = 1; j <= lat[i]; j++)
            fin >> obs[i][j].x >> obs[i][j].y;
    }
    fin >> pct[2].x >> pct[2].y;
    for(int i = 1; i <= m; i++)
        get_obstacol(obs[i], lat[i]);
    total_pct = 2;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= lat[i]; j++)
            pct[++total_pct] = obs[i][j];
    for(int i = 1; i <= total_pct; i++)
    {
        for(int j = i + 1; j <= total_pct; j++)
        {
            if(valid(pct[i], pct[j]))
            {
                double dist = get_dist(pct[i], pct[j]);
                if(dist < 0)
                    dist = -dist;
                G[i].push_back({j, dist});
                G[j].push_back({i, dist});
            }
        }
    }
    dijkstra();
    if(d[2] > inf/2)
        fout << "-1\n";
    else
        fout << fixed << setprecision(6) << d[2] << '\n';
    return 0;
}