## 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

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

### 3469 - Mission Impossible (WA)

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, inf;
Pto p; int r;
int m;

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=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;
zero(m);
forn(i, M)
forn(j, i)//draw lines joining centers
floodfill();
int best=-1;
double bdist=-1;
forn(j, N){//loop through all informants
bool inside=false;
forn(i, M)
inside=true; break;}
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;
}
``````