[COCI 2009/2010 – Constest #7 BAKICE]排序、模拟

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
。。。不想写了，等下有时间或许会补一下。
【算法分析】
看规模觉得很假。
于是直接暴力把所有点对取出来按距离排序。
然后贪心的取。
其实也不叫贪心了，应该说按题目那样模拟。
然后~，Orz，居然0MS AC了。。。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const int N=105;
const int INF=1000000000;
struct Queue{int x[N*N],y[N*N],t;}L,R;
struct edge{int x,y;}g[4000000];
bool v[N*N],Break[N*N];
int m,n,e,ans,link[N*N];
char c[N][N];

inline int dis(int i,int j){return sqr(L.x[i]-R.x[j])+sqr(L.y[i]-R.y[j]);}
inline int cmp(const void *x,const void *y){
return dis( ((edge*)x)->x, ((edge*)x)->y )
– dis( ((edge*)y)->x, ((edge*)y)->y );
}

void init(){
L.t=R.t=e=0;
int i,j;
scanf("%d%d",&m,&n);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
for (;c[i][j]!=’.’ && c[i][j]!=’X’ && c[i][j]!=’L’;c[i][j]=getchar());
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
if (c[i][j]==’X’){
L.t++;
L.x[L.t]=i;
L.y[L.t]=j;
}
else if (c[i][j]==’L’){
R.t++;
R.x[R.t]=i;
R.y[R.t]=j;
}
for (i=1;i<=L.t;i++)
for (j=1;j<=R.t;j++){
e++;
g[e].x=i; g[e].y=j;
}
qsort(&g[1],e,sizeof(edge),cmp);
}

void solve(){
memset(v,false,sizeof(v));
memset(link,0,sizeof(link));
memset(Break,false,sizeof(Break));
ans=0;
int i,j,k;
for (k=1;k<=e;k++){
i=g[k].x; j=g[k].y;
if (v[i]) continue;
if (!v[i] && !link[j]){
v[i]=true;
link[j]=i;
continue;
}
if (dis(i,j)==dis(link[j],j)){
if (!Break[j]) ans++;
Break[j]=true;
v[i]=true;
}
}
printf("%dn",ans);
}

int main(){
// freopen("bakice.in","r",stdin);
// freopen("bakice.out","w",stdout);
init();
solve();
}