問題
http://community.topcoder.com/stat?c=problem_statement&pm=11887&rd=14733
解き方
0.5単位のターンでぶつからないか試せば良い。
試す数の最大値に注意。
コード
class AntsMeet {
public: int countAnts(vector<int> x, vector<int> y, string direction) {
int n=x.size();
double dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int d[n];
FORE(i,0,n){
if(direction[i]=='E')d[i]=0;
if(direction[i]=='N')d[i]=1;
if(direction[i]=='W')d[i]=2;
if(direction[i]=='S')d[i]=3;
}
double px[n],py[n];
FORE(i,0,n){
px[i]=x[i];
py[i]=y[i];
}
int used[n];
memset(used,0,sizeof(used));
FORE(num,0,5000){
FORE(i,0,n){
px[i]+=dx[d[i]]*0.5;
py[i]+=dy[d[i]]*0.5;
}
FORE(i,0,n)if(!used[i]){
int update=0;
FORE(j,i+1,n)if(!used[j]){
if(px[i]==px[j] && py[i]==py[j]){
used[j]=1;
update=1;
}
}
if(update)used[i]=1;
}
}
int ret=0;
FORE(i,0,n)if(used[i])ret++;
return n-ret;
}
};
public: int countAnts(vector<int> x, vector<int> y, string direction) {
int n=x.size();
double dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int d[n];
FORE(i,0,n){
if(direction[i]=='E')d[i]=0;
if(direction[i]=='N')d[i]=1;
if(direction[i]=='W')d[i]=2;
if(direction[i]=='S')d[i]=3;
}
double px[n],py[n];
FORE(i,0,n){
px[i]=x[i];
py[i]=y[i];
}
int used[n];
memset(used,0,sizeof(used));
FORE(num,0,5000){
FORE(i,0,n){
px[i]+=dx[d[i]]*0.5;
py[i]+=dy[d[i]]*0.5;
}
FORE(i,0,n)if(!used[i]){
int update=0;
FORE(j,i+1,n)if(!used[j]){
if(px[i]==px[j] && py[i]==py[j]){
used[j]=1;
update=1;
}
}
if(update)used[i]=1;
}
}
int ret=0;
FORE(i,0,n)if(used[i])ret++;
return n-ret;
}
};