http://acm.pku.edu.cn/JudgeOnline/problem?id=1242
Код:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_N 100
typedef struct {
int row, col;
} Location;
int dist(Location l1, Location l2)
{
return abs(l1.row - l2.row) + abs(l1.col - l2.col) + 1;
}
void gen_plug(Location plug[MAX_N*MAX_N+1], int n)
{
int i, j, k;
k = 1;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
plug[k].row = i+1;
plug[k++].col = j+1;
}
}
}
void get_loc(int temp[MAX_N][MAX_N], Location socket[8][MAX_N*MAX_N+1],
int n, int k)
{
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
socket[k][temp[i][j]].row = i+1;
socket[k][temp[i][j]].col = j+1;
}
}
}
void gen_socket(Location socket[8][MAX_N*MAX_N+1], int n)
{
int temp[MAX_N][MAX_N];
int i, j, k;
k = 1;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 0);
k = 1;
for (j = n-1; j >= 0; j--) {
for (i = 0; i < n; i++) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 1);
k = 1;
for (i = n-1; i >= 0; i--) {
for (j = n-1; j >= 0; j--) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 2);
k = 1;
for (j = 0; j < n; j++) {
for (i = n-1; i >= 0; i--) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 3);
k = 1;
for (i = 0; i < n; i++) {
for (j = n-1; j >= 0; j--) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 4);
k = 1;
for (j = n-1; j >= 0; j--) {
for (i = n-1; i >= 0; i--) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 5);
k = 1;
for (i = n-1; i >= 0; i--) {
for (j = 0; j < n; j++) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 6);
k = 1;
for (j = 0; j < n; j++) {
for (i = 0; i < n; i++) {
temp[i][j] = k++;
}
}
get_loc(temp, socket, n, 7);
}
double avg_dist(Location plug[MAX_N*MAX_N+1], Location socket[MAX_N*MAX_N+1],
int from[MAX_N*MAX_N], int to[MAX_N*MAX_N], int m)
{
int i, sum = 0;
for (i = 0; i < m; i++) {
sum += dist(plug[from[i]], socket[to[i]]);
}
return (double)sum/m;
}
int main(void)
{
Location socket[8][MAX_N*MAX_N+1], plug[MAX_N*MAX_N+1];
int from[MAX_N*MAX_N], to[MAX_N*MAX_N];
int n, m, num, i;
double avg, best_avg;
num = 1;
while (scanf("%d", &n) == 1 && n) {
if (num > 1) {
printf("\n");
}
scanf("%d", &m);
for (i = 0; i < m; i++) {
scanf("%d %d", from+i, to+i);
}
gen_plug(plug, n);
gen_socket(socket, n);
best_avg = avg_dist(plug, socket[0], from, to, m);
for (i = 1; i < 8; i++) {
avg = avg_dist(plug, socket[i], from, to, m);
if (avg < best_avg) {
best_avg = avg;
}
}
printf("Scenario %d: smallest average = %.4f\n", num++, best_avg);
}
return 0;
}