rt,
我做了一道题,题目含义我不放了
代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y,N;
struct node{
int x;
int y;
}a[2005];
bool work1(ll n){
printf("do work1");
bool init[2005];
memset(init,sizeof(init),0);
int que[2005],quezuo=0,queyou=0;
memset(que,sizeof(que),0);
for(int i=1;i<=N;i++){
if(a[i].x-n+1<=0){
queyou++;
que[queyou]=i;
//init[i]=1;
if(a[i].x+n-1>=x||a[i].y-n+1<=0){
//printf("%d Die with 1_1 yes or no 1:%d yes or no 2:%d\n",n,a[i].x+n>=x,a[i].y-n<=0);
return 0;
}
}
}
while(quezuo<queyou){
int t=que[quezuo+1];
quezuo++;
for(int i=1;i<=N;i++){
//int t=sqrt(abs(a[x].x-a[i].x)*abs(a[x].x-a[i].x)+abs(a[x].y-a[i].y)*abs(a[x].y-a[i].y));
if(i==t)continue;
//cout<<" 111 "<<sqrt((a[t].x-a[i].x)*(a[t].x-a[i].x)+(a[t].y-a[i].y)*(a[t].y-a[i].y))<<endl;
if(!init[i]&&i!=t&&sqrt((a[t].x-a[i].x)*(a[t].x-a[i].x)+(a[t].y-a[i].y)*(a[t].y-a[i].y))<n*2){
queyou++;
que[queyou]=i;
init[i]=1;
if(a[i].x+n-1>=x||a[i].y-n+1<=0)return 0;
}
}
}
printf("%d ok1\n",n);
return 1;
}
bool work2(ll n){
printf("do work2");
bool init[2005];
memset(init,sizeof(init),0);
int que[2005],quezuo=0,queyou=0;
memset(que,sizeof(que),0);
for(int i=1;i<=N;i++){
if(a[i].y+n-1>=y){
queyou++;
que[queyou]=i;
//init[i]=1;
if(a[i].x+n-1>=x||a[i].y-n+1<=0)return 0;
}
}
while(quezuo<queyou){
int t=que[quezuo+1];
quezuo++;
for(int i=1;i<=N;i++){
//cout<<sqrt(abs(a[x].x-a[i].x)*abs(a[x].x-a[i].x)+abs(a[x].y-a[i].y)*abs(a[x].y-a[i].y));
if(!init[i]&&i!=t&&sqrt((a[t].x-a[i].x)*(a[t].x-a[i].x)+(a[t].y-a[i].y)*(a[t].y-a[i].y))<n*2){
queyou++;
que[queyou]=i;
init[i]=1;
if(a[i].x+n-1>=x||a[i].y-n+1<=0)return 0;
}
}
}
printf("%d ok2\n",n);
return 1;
}
bool work(ll n){
return work1(n)&&work2(n);
}
int main(){
//freopen("creed.in","r",stdin);
//freopen("creed.out","w",stdout);
scanf("%lld%lld%lld",&x,&y,&N);
x*=100;y*=100;
for(ll i=1;i<=N;i++){
int X,Y;
scanf("%d%d",&X,&Y);
a[i].x=X*100;
a[i].y=Y*100;
//printf("a[%d].x=%d a[%d].x=%d\n",i,a[i].x,i,a[i].y);
}
ll l=0,r=min(x,y),ans=0;
while(l<=r){
int mid=(l+r)/2;
if(work(mid)){
ans=mid;
l=mid+1;
}
else {
r=mid-1;
}
}
printf("%.2lf",ans/(double)100);
}
//这是特殊样例
/*
3 3 2
1 2
2 1
*/
这个时候问题就出现了
如果我把
//cout<<" 111 "<<sqrt((a[t].x-a[i].x)*(a[t].x-a[i].x)+(a[t].y-a[i].y)*(a[t].y-a[i].y))<<endl;
的//删掉,答案(特定样例)会由错误的1.49变成正确的1.00(luogu IDE 上会出现1.11)!!
我已经试了三台电脑了,求大神帮忙解决一下