这题没什么好说的。。求一个组合体的质心，还是采取公式
诡异的是这道题在TOJ上过不去。。orz..
1
# include <iostream>
2# include <cstdio>
3# include <vector>
4using namespace std;
5char map[300][300];
6int c,r;
7void dfs(int i,int j,double &x,double &y,int &total)
8
{
9
if(i<0||i>=r||j<0||j>c||map[i][j]=='.') return;
10 map[i][j]='.';
11 total++;
12 x+=(2*i+1)/2.0;
13 y+=(2*j+1)/2.0;
14 dfs(i-1,j,x,y,total);
15 dfs(i+1,j,x,y,total);
16 dfs(i,j-1,x,y,total);
17 dfs(i,j+1,x,y,total);
18
19
}
20int main()
21{
22 while(true)
23
{
24 vector<double> x,y;
25 scanf("%d%d",&c,&r);
26 if(!c&&!r) break;
27 while(true)
28 {
29 int maxnum=-1;
30 double totalx=0,totaly=0;
31 for(int i=0;i<r;i++)
32 scanf("%s",map[i]);
33 for(int i=0;i<r;i++)
34 for(int j=0;j<c;j++)
35 if(map[i][j]=='x')
36 {
37 double nowx=0,nowy=0;
38 int total=0;
39 dfs(i,j,nowx,nowy,total);
40 if(total>maxnum)
41 {
42 maxnum=total;
43 totalx=nowx;
44 totaly=nowy;
45
}
46 }
47 x.push_back((totalx)/maxnum);
48 y.push_back((totaly)/maxnum);
49 scanf("%s",map[0]);
50 if(map[0][0]=='=') break;
51 }
52 double resx=0,resy=0;
53 int T=x.size()/2;
54 for(int i=0;i<x.size()-T;i++)
55 {
56 resx+=(x[i+T]-x[i])/T;
57 resy+=(y[i+T]-y[i])/T;
58 }
59 resx/=T;
60 resy/=T;
61 printf("%.2f %.2f\n",resy+1e-6,resx+1e-6);
62 }
63 return 0;
64}
65
66