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