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;
}