10762 - Treasure Castle

[BiK]

I like this problem but unfortunately don't know how to solve it. Could you explain the idea of the solution?

[edans]

The main ideia is: create any path and try to make it better.

to create a path you can walk by the walls from the entrance until the treasure. This path will be hardly the optimal.

to optimize the path you may apply 2 optimizations:

first: delete colinear adjacent points
second: Optimize the "U"'s. An "U" means 3 segments with U shape (e.g. UP, LEFT, DOWN). An U can be optimized as reducing its height or deleting one of its segments.

you may do that until we cant do any optimizations.

[Krzysztof Duleba]

I used a different approach - a simple BFS. The only thing you have to do is to skip irrelevant points. The solution works in O(n^2), where n is the number of castles.

[Destination Goa]

edans,

How do you check that reducing U-turn will not cause crossing some wall? I don't think that N^2 solution was author's intention... Also all AC solutions run at very low times. What was time complexity of your solution? And do you have AC now?

[Destination Goa]

edans,

Just implemented your method at O(N^2). The only optimization was doubly linked list for path (it's easier to write anyway). After removing run-time check-ups got 0.000 sec with 350 lines of rough code and lots of small oftenly called routines. How can this be??? Is there at least one spiral or snake test for N>=1000?

[little joey]

The description is extremely misleading (or equivalently the input is extremely weak). I assumed that N<128 and got accepted in 0.002 with an O(N^4), which means that N is probably even much smaller.
I doubt that this problem is solvable in time for values of N in the thousands. I spent a lot of time thinking about this problem, so I realy feel cheated by such small input...

[Krzysztof Duleba]

O(n^2) will work fine even for n = 5000. Why do you doubt it?

[little joey]

Maybe it's because I don't understand how it's done in O(N^2), so it is just based on an estimation and the fact that none of the accepted programs had to prove themselves on input that big.
I'd be more than happy if you could explain me your algorithm and take away my doubts.

[Krzysztof Duleba]

The most straightforward solution is a flood fill. But here there are 10000 * 10000 grid points - too many.
The key thought is to see that most grid points are useless - we can create a new grid erasing all those lines that do not cross any castle. There will be O(n^2) new grid points and properly implemented flood fill will run in O(n^2).

[little joey]

Duh. [Knocks himself on the head with a hammer]
Yes of course you're right. I also implemented this 'reduced grid', but then erroniously rejected flood fill and did a simple Dijkstra instead. But now that I think about it again, I understand that flood fill will always give the shortest distance to the entrance point (because the walls form a polygon so there are no interior walls).
Thanks for enlightening me, I was being stupid.

[Cho]

The reduced grid is no doubt one of the first approaches those came to my mind after I read the problem (almost 1.5 years ago?). But I missed the point that flood fill on this grid will work. Don't know what I was thinking all these months. Thanks for pointing that out, Krzysztof.
(And the ':' character costs me almost 10 WA. Sigh...)

Now 98 down in v107.
I finally get one volume to be tied with the top of the world

[sclo]

I've just used assert to check the inputsize. I got AC with only a gridsize of 10x10. The input is extremely weak. Actually, it should be 8x8 because I used both +inf and -inf also as grid points.

[viniciusjssouza]

I'm trying to solve this problem but i only get TLE. A changed my algorithm several times and my final algorithm is the best in performance. I implemented the A-star algorithm, with the manhatanian distance plus the number of steps being the value inserted in the priority queue. To skip the irrelevant points, i used the point-in-polygon algorithm. After the optimization, i still got i TLE. My code follows below.

Code: Select all

#include<iostream>
#include<vector>
#include<cmath>
#include<deque>
#include<map>
#include<set>

#define INSIDE	1  
#define OUTSIDE 0
#define BOUNDARY -1

#define MAXV  10000
#define INF 0x7FFFFFFF

using namespace std;

const double EPS = 1e-10;
inline int cmp(double x, double y = 0, double tol = EPS) 
{     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;  }

struct Point 
{
   double x, y;  
   Point(double x=0.0, double y=0.0):x(x), y(y){}
};
typedef vector<Point> Polygon;
typedef pair<Point, int> pi;
Point entrance, treasure;

/* Produto interno dos vetores AB e BC */
double dot(Point &a, Point &b, Point &c)
{
   Point ab((b.x-a.x), (b.y-a.y));
   Point bc((c.x-b.x), (c.y-b.y));
   return (ab.x * bc.x + ab.y * bc.y);
}

/* Produto vetorial dos vetores AB e AC -> AB x AC */
double cross(Point &a, Point &b, Point &c)
{
   Point ab((b.x-a.x), (b.y-a.y));
   Point ac((c.x-a.x), (c.y-a.y));
   return (ab.x * ac.y - ab.y * ac.x);
}

double euclidianDist(Point &a, Point &b)
{
   return sqrt((double)pow((a.x-b.x), 2.0) + (double)pow((a.y-b.y), 2.0));
}

/* Distancia do ponto p ao segmento formado por AB */
double distPointToSegment(Point &a, Point &b, Point &c)
{
   double dist = cross(a, b, c) / euclidianDist(a, b);
   int dot1 = dot(a,b,c);
   if (dot1 > 0) return euclidianDist(b,c);
   int dot2 = dot(b, a, c);
   if (dot2 > 0) return euclidianDist(a,c);
   return abs(dist);
}

int inPolygon(Polygon &polygon, Point p)
{
   int counter = 0;
   int N = polygon.size();
   double xinters;
   Point p1 = polygon[0];
   for (int i=1; i<=N ;i++) 
   {
      Point p2 = polygon[i % N];
      double dist = distPointToSegment(p1, p2, p);
      if (cmp(dist) == 0)
	 return BOUNDARY;
      if (p.y > min(p1.y,p2.y)) 
      {
	 if (p.y <= max(p1.y,p2.y)) 
	 {
	    if (p.x <= max(p1.x,p2.x)) 
	    {
	       if (p1.y != p2.y) 
	       {
		  xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
		  if (p1.x == p2.x || p.x <= xinters)
		     counter++;
	       }
	    }
	 }
      }
      p1 = p2;
   }
   if (!(counter & 1))
      return(OUTSIDE);
   else
      return(INSIDE);
}

struct CmpPi
{
   bool operator()(const pi &a, const pi &b)
   {
      return (a.second <= b.second);
   }
};
/* Distancia Manhataniana */
int calculDist(Point &p)
{
   return (abs(p.x - treasure.x) + abs(p.y - treasure.y));
}

void insertQueue(map<int, map<int,int> > &castle, Polygon &poly,  map<int, bool> &segX, map<int,bool> &segY, Point next, Point nextHalf, Point &current, set<pi, CmpPi> &fila)
{
   if (castle[(int)next.x+MAXV][(int)next.y+MAXV] && castle[(int)next.x+MAXV][(int)next.y+MAXV] <= castle[(int)current.x+MAXV][(int)current.y+MAXV]+1)
      return;
   if ( (segX[next.x] || segY[next.y]) &&      
	  (inPolygon(poly, next) == OUTSIDE || inPolygon(poly, nextHalf) == OUTSIDE))
	    return;
   fila.insert(pi(next, castle[(int)current.x+MAXV][(int)current.y+MAXV]+1 + calculDist(next) ));
   castle[(int)next.x+MAXV][(int)next.y+MAXV] = castle[(int)current.x+MAXV][(int)current.y+MAXV]+1;
}

int aStar(Polygon &poly, map<int, bool> &segX, map<int,bool> &segY)
{
   map<int, map<int,int> > castle; 
   set<pi, CmpPi> fila;
   fila.insert(pi(entrance,calculDist(entrance)));
   castle[(int)entrance.x+MAXV][(int)entrance.y+MAXV] = 0;
   int minimo = INF;
   
   while (!fila.empty())
   {	
      pi par = *fila.begin();
      Point current = par.first;
      //printf("Entrei (%lf, %lf)\n", current.x, current.y);
      
      fila.erase(fila.begin());
      if (par.second >= minimo) continue;
      if (current.x == treasure.x && current.y == treasure.y)
      {
	 if (castle[(int)current.x+MAXV][(int)current.y+MAXV] < minimo)
	    minimo = castle[(int)current.x+MAXV][(int)current.y+MAXV];
	 continue;
      }
      insertQueue(castle, poly, segX, segY, Point(current.x+1, current.y), Point(current.x+0.5, current.y), current, fila);
      insertQueue(castle, poly, segX, segY, Point(current.x, current.y-1), Point(current.x, current.y-0.5), current, fila);
      insertQueue(castle, poly, segX, segY, Point(current.x-1, current.y), Point(current.x-0.5, current.y), current, fila);
      insertQueue(castle, poly, segX, segY, Point(current.x, current.y+1), Point(current.x, current.y-0.5), current, fila); 
   }
   return minimo;
}

int main()
{
   //long st = clock();
   int id = 0;
   while(true)
   {
      int N;
      id++;
      scanf("%d", &N);
      if (!N) break;
      Polygon poly(N);
      map<int, bool> segX;
      map<int, bool> segY;
      for (int i = 0; i < N; i++)
      {
	 scanf("%lf %lf", &poly[i].x, &poly[i].y);
	 segX[poly[i].x] = true;
	 segY[poly[i].y] = true;
      }
      scanf("%lf %lf", &entrance.x, &entrance.y);
      scanf("%lf %lf", &treasure.x, &treasure.y);
      printf("Castle %d: %d\n", id, aStar(poly, segX, segY));
   }
   //cout << (double)((double)(clock()-st) / (double)CLOCKS_PER_SEC) << endl;
}