3469 - Mission Impossible (WA)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
jorgedro
New poster
Posts: 1
Joined: Tue Jun 24, 2014 4:42 am

3469 - Mission Impossible (WA)

Post by jorgedro » Tue Jun 24, 2014 7:17 am

https://icpcarchive.ecs.baylor.edu/inde ... oblem=1470

I'm getting WA. Here's my approach:
I create a grid(coordinates values are small enough) where i draw a line(using bresenham) between two radar centers IF those radars are intersecting each other. Then i do a flood fill starting from a corner which is "stopped" by the lines. The cells that remain not colored are those who are sorrounded with lines, i.e they are sorrounded by radars.

-An informer can be reached if is not inside a radar AND his cell isn't colored.
-The distance to the polygon, and the rest of the problem seems trivial.

I'll highly appreciate input cases or other suggestions. Thanks!

Here's my code so far:

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <queue>
using namespace std;
#define forr(i, a, b) for(int i=(a); i<(b); i++)
#define forn(i, n) forr(i, 0, n)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
#define INF 99999999

int B, N, M, M2;
struct Pto{
	int x, y;
	Pto(){}
	Pto(int x, int y):x(x),y(y){}
	Pto operator+(Pto a){return Pto(x+a.x, y+a.y);}
	Pto operator-(Pto a){return Pto(x-a.x, y-a.y);}
	Pto operator+(int a){return Pto(x+a, y+a);}
	Pto operator*(int a){return Pto(x*a, y*a);}
	bool operator==(Pto a){return y==a.y&&x==a.x;}
	double norm(){return sqrt(x*x+y*y);}
	int norm_sq(){return x*x+y*y;}
};
typedef Pto Vec;
int cross(Vec a, Vec b){return a.x*b.y-a.y*b.x;}
int dist_sq(Pto a, Pto b){return (b-a).norm_sq();}

#define EPS 1e-9
double distSegm(Pto v, Pto w, Pto p) {//dist from p to segment vw
	double l2 = dist_sq(w, v);
	if(fabs(l2)<EPS) return dist_sq(v, p);
	double t = cross(p-v, w-v)/l2;
	if (t < EPS) return dist_sq(p, v);
	else if (t-1 > -EPS) return dist_sq(p, w);
	double ax=p.x-v.x+(w.x - v.x)*t;
	double ay=p.y-v.y+(w.y - v.y)*t;
	return ax*ax+ay*ay;
}

Pto b[1010], inf[1010];
struct Radar{
	Pto p; int r;
} rad[35];
int m[1010][1010];

void bresenham(Pto a, Pto b){
	Pto d=b-a; d.x=abs(d.x), d.y=abs(d.y);
	Pto s(a.x<b.x? 1: -1, a.y<b.y? 1: -1);
	int err=d.x-d.y;
	while(1){
		m[a.x][a.y]=1;//plot
		if(a==b) break;
		int e2=2*err;
		if(e2 > -d.y){ 
			err-=d.y;
			a.x+=s.x;
		}
		if(e2 < d.x){
			err+= d.x;
			a.y+= s.y;
		}
	}
}

Pto dxy[]={Pto(0, 1), Pto(1, 0), Pto(0, -1), Pto(-1, 0)};
void floodfill(){
	queue<Pto> cola;
	m[0][0]=1;
	cola.push(Pto(0, 0));
	while(sz(cola)){
		Pto v=cola.front(); cola.pop();
		forn(d, 4){
			Pto dst=v+dxy[d];
			if(0<=dst.x&&dst.x<1010 && 0<=dst.y&&dst.y<1010 && !m[dst.x][dst.y]){
				m[dst.x][dst.y]=1;
				cola.push(dst);
			}
		}
	}
}

int main()
{
	while(cin >> B, B){
		forn(i, B) cin >> b[i].x >> b[i].y;
		cin >> N;
		forn(i, N) cin >> inf[i].x >> inf[i].y;
		cin >> M;
		forn(i, M) cin >> rad[i].p.x >> rad[i].p.y >> rad[i].r;
		zero(m);
		forn(i, M)
			forn(j, i)//draw lines joining centers
				if(dist_sq(rad[i].p, rad[j].p)<=(rad[i].r+rad[j].r)*(rad[i].r+rad[j].r))
					bresenham(rad[j].p+1, rad[i].p+1);//map has offset 1
		floodfill();		
		int best=-1;
		double bdist=-1;
		forn(j, N){//loop through all informants
			if(!m[inf[j].x+1][inf[j].y+1]) continue;//is sorrounded by radars
			bool inside=false;
			forn(i, M)
				if(dist_sq(rad[i].p, inf[j])<=rad[i].r*rad[i].r){
					inside=true; break;}
			if(inside) continue;//inside a radar
			double dist=INF;
			forn(i, B)//dist to polygon
				dist=min(dist, distSegm(b[i], b[(i+1)%B], inf[j]));
			if(dist-bdist>EPS){
				best=j;
				bdist=dist;
			}
		}
		if(best==-1) cout << "Mission impossible" << endl;
		else cout << "Contact informer " << best+1 << endl;//offset
	}
    return 0;
}

Post Reply

Return to “ACM ICPC Archive Board”