# 28 条题解

• @ 2017-10-08 14:32:15
``````#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<cmath>
#include<cstring>
#define maxa 200+10
#define FOR(i,x,y) for(i=x;i<=y;++i)
using namespace std;
struct point
{
int x,y;
};
struct node
{
string name;
vector<point> v;
double d;
}e[maxa];
double dis(point p,point q)
{
return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}
bool comp(node p,node q)
{
if(p.d!=q.d)
{
return p.d<q.d;
}
else
return p.name<q.name;
}
int main()
{
int n,m,l;
scanf("%d%d%d",&n,&m,&l);
int mod = 260;
char s[mod];
int i,j,k;
for(i=0;i<n;++i)
{

scanf("%s",s);
for(j=0;j<m;++j)
if(s[j]=='#')
{
e[0].v.push_back(point{i,j});
}
}
FOR(i,1,l)
{
scanf("%s",s);
e[i].name = s;
FOR(k,0,n-1){
scanf("%s",s);
FOR(j,0,m-1)
if(s[j]=='#')
{
e[i].v.push_back(point{k,j});
}
}
double ans = 0;
FOR(j,0,e[i].v.size()-1){
double tot = maxa*10;
FOR(k,0,e[0].v.size()-1)
if(dis(e[0].v[k],e[i].v[j])<tot)
{
tot = dis(e[0].v[k],e[i].v[j]);
}
if(tot>ans)
ans = tot;
}
e[i].d = ans;
}
sort(e+1,e+l+1,comp);
FOR(i,1,l)
{
cout<<e[i].name<<endl;
cout<<fixed<<setprecision(5)<<e[i].d<<endl;
}
return 0;
}

``````
• @ 2017-07-08 16:36:56

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
{
int x=0;char c;int f=1;
for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0';
return x*f;
}

struct nio{
double maxx;
string h;
}st[250];
bool comp(const nio &a,const nio &b)
{
if(a.maxx!=b.maxx)return a.maxx<b.maxx;
return a.h<b.h;
}
struct node{
int x,y;
}sc[10005];
int n,m,l;double dis[105][105];
int tot=0;
bool sign[105][105];

int main()
{
//freopen("x.in","r",stdin);
char s,h[260];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dis[i][j]=1e+9;
cin>>s;
if(s=='#'){
sc[++tot].x=i;
sc[tot].y=j;
}
}

for(int i=1;i<=l;i++)
{
st[i].maxx=-1;
cin>>st[i].h;
for(int j=1;j<=n;j++)
{
for(int k=1;k<=m;k++)
{
cin>>s;
if(s=='#'){
if(!sign[j][k])
{
for(int g=1;g<=tot;g++)
{
double len=sqrt((sc[g].x-j)*(sc[g].x-j)+(sc[g].y-k)*(sc[g].y-k));
dis[j][k]=min(dis[j][k],len);
sign[j][k]=1;
}
}
st[i].maxx=max(st[i].maxx,dis[j][k]);
}
}
}
}
sort(st+1,st+l+1,comp);
for(int i=1;i<=l;i++)
{
cout<<st[i].h<<endl;
printf("%.5f\n",st[i].maxx);
}
}

• @ 2009-11-10 00:55:46

这个，排序已经改成描述的双关键字了………………

预处理学校到每个'.'的最近距离，DFS一下，记忆化搜索。

后面就直接读结果比较一下取最大值，最后双关键字排序，都是小菜一碟。

这题差点把我做残了，郁闷。

• @ 2009-11-09 14:08:42

枚举，O(nml^2)，过了。。。

• @ 2009-11-06 20:53:15

各位大哥大姐，这里是写题解的地方，请不要乱贴 东西，这样会 浪费初学者的时间。

请各位多多合作，谢谢！

• @ 2009-11-04 17:31:00

原本 是单关建字 的

有改过来了 郁闷

• @ 2009-11-03 00:09:22

受不了了，一样的代码

比赛时测是30，现在AC

• @ 2009-11-02 06:53:14
• -难怪我怎么感觉快排打错出现30分- -
囧到了
原来是数据问题啊
• @ 2009-11-01 23:39:27

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

呵呵！~~~rp++啊，秒掉！

• @ 2009-11-01 19:09:38

太搞笑了，标程都30，看到他双关键字排序了。

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 05：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 06：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 11：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 14：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 17：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 18：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 19：答案错误...程序输出比正确答案长

├ 测试数据 20：答案错误...　├ 标准行输出

├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：30 有效耗时：0ms

• @ 2009-11-01 15:29:45

题目出的真好，只要按题目做就是30分，无视句话就AC，原来为了压分数还可以这么做，了得了得。

• @ 2009-11-01 14:51:10

数据好弱

• @ 2009-11-01 13:34:56

数据绝对有问题...

30分的,双关键字快排改冒泡按距离排序就AC

• @ 2009-11-01 00:06:18

数据我可以说没有问题……

程序完全可以秒杀

• @ 2009-10-31 21:03:22

垃圾数据

• @ 2009-10-31 20:43:18

BS

办比赛能不能把数据出正确啊

第一题 VJ接受不了

第二题 数据有错

真是受不了

• @ 2009-10-31 16:28:31

见面不如闻名``\`

• @ 2009-10-31 16:19:01

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 56ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：56ms

• -
没有秒杀~~~
最后好像快排是过不了的，
好像要冒泡或选择才能过
• @ 2009-10-31 16:17:44

Accepted 有效得分：100 有效耗时：0ms

确实很阴

• @ 2009-10-31 15:17:59

不用按名字顺序排，用冒泡排大小就行！！！

好阴的数据，好阴的题！！！！！！

ID
1650

8

692

78

11%

1