Mai intai trebuie sa te autentifici.

Cod sursa(job #324061)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 14 iunie 2009 15:32:09
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 59.07 kb
#include <cstdio>                                                                                                                                                                              
#include <cstdlib>                                                                                                                                                                              
#include <cstring>                                                                                                                                                                              
#include <math.h>                                                                                                                                                                              
#include <vector>                                                                                                                                                                              
#include <algorithm>                                                                                                                                                                              
                                                                                                                                                                              
using namespace std;                                                                                                                                                                              
                                                                                                                                                                              
#define sz(a) int((a).size())                                                                                                                                                                              
#define pb push_back                                                                                                                                                                              
#define mp make_pair                                                                                                                                                                              
#define x first                                                                                                                                                                              
#define y second                                                                                                                                                                              
#define punct pair<int, int>                                                                                                                                                                              
#define punct2 pair<double, double>                                                                                                                                                                              
#define tr(c, it) for (typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)                                                                                                                                                                              
#define all(c) (c).begin(), (c).end()                                                                                                                                                                              
                                                                                                                                                                              
#define inf 1e9                                                                                                                                                                              
#define Pmax 2600                                                                                                                                                                              
                                                                                                                                                                              
punct finish;                                                                                                                                                                              
vector< punct > robot;                                                                                                                                                                              
vector< vector< punct> > obstacol;                                                                                                                                                                              
                                                                                                                                                                              
char viz[Pmax];                                                                                                                                                                              
int st[Pmax];                                                                                                                                                                              
                                                                                                                                                                              
vector< punct > v;                                                                                                                                                                              
punct2 inter;                                                                                                                                                                              
                                                                                                                                                                              
void readdata() {                                                                                                                                                                              
freopen("robot.in", "r", stdin);                                                                                                                                                                              
freopen("robot.out", "w", stdout);                                                                                                                                                                              
                                                                                                                                                                              
int i, j, a, b, n, m;                                                                                                                                                                              
vector<punct> aux;                                                                                                                                                                              
                                                                                                                                                                              
scanf("%d", &n);                                                                                                                                                                              
for (i = 0; i < n; ++i) {                                                                                                                                                                              
scanf("%d %d", &a, &b);                                                                                                                                                                              
robot.pb( mp(a, b) );                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
scanf("%d", &m);                                                                                                                                                                              
for (i = 1; i <= m; ++i) {                                                                                                                                                                              
scanf("%d", &n);                                                                                                                                                                              
for (aux.clear(), j = 0; j < n; ++j) {                                                                                                                                                                              
scanf("%d %d", &a, &b);                                                                                                                                                                              
aux.pb( mp(a, b) );                                                                                                                                                                              
}                                                                                                                                                                              
obstacol.pb(aux);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
scanf("%d %d", &finish.x, &finish.y);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int sign(punct a, punct b, punct c) {                                                                                                                                                                              
int prod = (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);                                                                                                                                                                              
return (prod == 0 ? 0 : prod < 0 ? -1 : 1);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
void convex_hull(vector< punct > &v) {                                                                                                                                                                              
int i, p = 1, n;                                                                                                                                                                              
vector< punct> aux;                                                                                                                                                                              
                                                                                                                                                                              
sort( all(v) );                                                                                                                                                                              
v.resize( unique(all(v)) - v.begin() );                                                                                                                                                                              
                                                                                                                                                                              
n = sz(v);                                                                                                                                                                              
memset(viz, 0, sizeof(viz));                                                                                                                                                                              
st[ st[0] = 1 ] = 0;                                                                                                                                                                              
for (i = 1; i >= 0; i += (p = (i == n-1) ? -p : p))                                                                                                                                                                              
if (!viz[i]) {                                                                                                                                                                              
while (st[0] >= 2 && sign(v[i], v[st[ st[0] ]], v[st[ st[0]-1 ]]) <= 0)                                                                                                                                                                              
viz[ st[ st[0]-- ] ] = 0;                                                                                                                                                                              
viz[ st[++st[0]] = i ] = 1;                                                                                                                                                                              
}                                                                                                                                                                              
for (i = 1; i < st[0]; ++i)                                                                                                                                                                              
aux.pb(v[st[i]]);                                                                                                                                                                              
v = aux;                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
void refa_obstacol(vector< punct > &v) {                                                                                                                                                                              
int i, j, lim = sz(v);                                                                                                                                                                              
                                                                                                                                                                              
for (i = 0; i < lim; ++i)                                                                                                                                                                              
for (j = 0; j < sz(robot); ++j)                                                                                                                                                                              
v.pb( mp(v[i].x + robot[0].x - robot[j].x, v[i].y + robot[0].y - robot[j].y) );                                                                                                                                                                              
convex_hull(v);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
void refa_finish() {                                                                                                                                                                              
int best = robot[0].y;                                                                                                                                                                              
tr(robot, it) best = min(best, it->y);                                                                                                                                                                              
finish.y += robot[0].y-best;                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
inline double sqr(int a) {                                                                                                                                                                              
return double(a*a);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int apartine(punct a, punct b, punct c) {                                                                                                                                                                              
punct p1 = min(b, c), p2 = max(b, c);                                                                                                                                                                              
                                                                                                                                                                              
return ((a.y-p1.y)*(p2.x-p1.x) == (a.x-p1.x)*(p2.y-p1.y) && a >= p1 && a <= p2);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int coliniar(punct a, punct b, punct c) {                                                                                                                                                                              
return (a.y-b.y)*(c.x-b.x) == (a.x-b.x)*(c.y-b.y);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int contur(punct a, vector< punct > &v) {                                                                                                                                                                              
for (int i = 0; i < sz(v)-1; ++i)                                                                                                                                                                              
if (apartine(a, v[i], v[i+1]))                                                                                                                                                                              
return 1;                                                                                                                                                                              
return 0;                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int arie_poligon(vector< punct > &v) {                                                                                                                                                                              
int ret = 0, i;                                                                                                                                                                              
for (i = 0; i < sz(v)-1; ++i)                                                                                                                                                                              
ret += v[i].x*v[i+1].y - v[i+1].x*v[i].y;                                                                                                                                                                              
return abs(ret);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int arie_punct(punct a, vector< punct > &v) {                                                                                                                                                                              
vector< punct > aux;                                                                                                                                                                              
int ret = 0, i;                                                                                                                                                                              
                                                                                                                                                                              
for (i = 0; i < sz(v)-1; ++i) {                                                                                                                                                                              
aux.clear();                                                                                                                                                                              
aux.pb(v[i]), aux.pb(v[i+1]), aux.pb(a);                                                                                                                                                                              
aux.pb(v[i]);                                                                                                                                                                              
ret += arie_poligon(aux);                                                                                                                                                                              
}                                                                                                                                                                              
return ret;                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int intersection(punct a, punct b, punct c, punct d) {                                                                                                                                                                              
double A, B, C, A2, B2, C2, det;                                                                                                                                                                              
                                                                                                                                                                              
A = b.y-a.y;                                                                                                                                                                              
B = a.x-b.x;                                                                                                                                                                              
C = -a.y*(b.x-a.x) + a.x*(b.y-a.y);                                                                                                                                                                              
                                                                                                                                                                              
A2 = d.y-c.y;                                                                                                                                                                              
B2 = c.x-d.x;                                                                                                                                                                              
C2 = -c.y*(d.x-c.x) + c.x*(d.y-c.y);                                                                                                                                                                              
                                                                                                                                                                              
det = A*B2 - B*A2;                                                                                                                                                                              
if (det == 0) return 0;                                                                                                                                                                              
inter = mp( (B2*C - B*C2)/det, (A*C2 - A2*C)/det );                                                                                                                                                                              
                                                                                                                                                                              
return (sign(c, b, a) * sign(d, b, a) <= 0 && sign(a, c, d) * sign(b, c, d) <= 0);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int intersecteaza(punct a, punct b, vector< punct > &v) {                                                                                                                                                                              
int i;                                                                                                                                                                              
                                                                                                                                                                              
//cazul in care a si b apartin dreptei suport a unei laturi                                                                                                                                                                              
for (i = 0; i < sz(v)-1; ++i)                                                                                                                                                                              
if (coliniar(a, v[i], v[i+1]) && coliniar(b, v[i], v[i+1]))                                                                                                                                                                              
return 0;                                                                                                                                                                              
                                                                                                                                                                              
//afla care din puncte se afla pe conturul poligonului                                                                                                                                                                              
char v1 = contur(a, v), v2 = contur(b, v);                                                                                                                                                                              
if (v1 && v2) return 1;                                                                                                                                                                              
                                                                                                                                                                              
//cazul in care un punct apartine interiorului poligonului                                                                                                                                                                              
int ap = arie_poligon(v), a1 = arie_punct(a, v), a2 = arie_punct(b, v);                                                                                                                                                                              
if (a1 == ap && !v1) return 1;                                                                                                                                                                              
if (a2 == ap && !v2) return 1;                                                                                                                                                                              
                                                                                                                                                                              
vector< punct2 > aux;                                                                                                                                                                              
for (i = 0; i < sz(v)-1; ++i)                                                                                                                                                                              
if (intersection(a, b, v[i], v[i+1]))                                                                                                                                                                              
aux.pb(inter);                                                                                                                                                                              
sort(all(aux));                                                                                                                                                                              
aux.resize( unique(all(aux)) - aux.begin() );                                                                                                                                                                              
                                                                                                                                                                              
return sz(aux) > 1;                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
double afla_distanta(punct a, punct b) {                                                                                                                                                                              
double ret = sqrt(sqr(a.x-b.x) + sqr(a.y-b.y));                                                                                                                                                                              
int i;                                                                                                                                                                              
                                                                                                                                                                              
if (a == b) return ret;                                                                                                                                                                              
for (i = 0; i < sz(obstacol); ++i)                                                                                                                                                                              
if (intersecteaza(a, b, obstacol[i]))                                                                                                                                                                              
return inf;                                                                                                                                                                              
return ret;                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
void solve() {                                                                                                                                                                              
int i, j;                                                                                                                                                                              
                                                                                                                                                                              
//redu robotul la un singur punct;                                                                                                                                                                              
sort(all(robot));                                                                                                                                                                              
for (i = 0; i < sz(obstacol); ++i)                                                                                                                                                                              
refa_obstacol(obstacol[i]);                                                                                                                                                                              
refa_finish();                                                                                                                                                                              
                                                                                                                                                                              
//afla punctele ce pot fi vizitate si matricea de adiacenta                                                                                                                                                                              
v.pb(robot[0]);                                                                                                                                                                              
for (i = 0; i < sz(obstacol); ++i)                                                                                                                                                                              
for (j = 0; j < sz(obstacol[i]); ++j)                                                                                                                                                                              
v.pb(obstacol[i][j]);                                                                                                                                                                              
v.pb(finish);                                                                                                                                                                              
                                                                                                                                                                              
vector< vector< double > > c( sz(v), sz(v) );                                                                                                                                                                              
                                                                                                                                                                              
for (i = 0; i < sz(obstacol); ++i)                                                                                                                                                                              
obstacol[i].pb( obstacol[i][0] );                                                                                                                                                                              
                                                                                                                                                                              
for (i = 0; i < sz(v); ++i)                                                                                                                                                                              
for (j = 0; j < sz(v); ++j)                                                                                                                                                                              
c[i][j] = afla_distanta(v[i], v[j]);                                                                                                                                                                              
                                                                                                                                                                              
//afla drumul cel mai scurt si afiseaza                                                                                                                                                                              
int n = sz(v)-1;                                                                                                                                                                              
vector< double > d(n+1, inf);                                                                                                                                                                              
vector< char > viz(n+1, 0);                                                                                                                                                                              
                                                                                                                                                                              
double best;                                                                                                                                                                              
int poz;                                                                                                                                                                              
                                                                                                                                                                              
d[0] = 0;                                                                                                                                                                              
while (!viz[n]) {                                                                                                                                                                              
best = inf;                                                                                                                                                                              
for (i = 0; i <= n; ++i)                                                                                                                                                                              
if (!viz[i] && d[i] < best) {                                                                                                                                                                              
best = d[i];                                                                                                                                                                              
poz = i;                                                                                                                                                                              
}                                                                                                                                                                              
viz[poz] = 1;                                                                                                                                                                              
for (i = 0; i <= n; ++i)                                                                                                                                                                              
d[i] = min(d[i], best + c[poz][i]);                                                                                                                                                                              
}                                                                                                                                                                              
printf("%lfn", d[n]);                                                                                                                                                                              
}                                                                                                                                                                              
                                                                                                                                                                              
int main() {                                                                                                                                                                              
readdata();                                                                                                                                                                              
solve();                                                                                                                                                                              
return 0;                                                                                                                                                                              
}