Submission #1545706

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define ls (node<<1)
#define rs (node<<1|1)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long double ld;
const int N=200005;
int n=0,xl,xr,yl,yr,m;ld f[N];
ld inf=2e15;
struct node{
	int x,y;
	bool operator <(const node &pp)const{
		if(x!=pp.x)return x<pp.x;
		return y<pp.x;
	}
}a[N];
ld pi=acos(-1.0),p1=5*pi,p2=10*pi,Tree[N<<2];int b[N];
void upd(int node){
	Tree[node]=Min(Tree[ls],Tree[rs]);
}
void updata(int l,int r,int node,int sa,ld to){
	if(l>sa || r<sa)return ;
	if(l==r){
		if(Tree[node]>to)Tree[node]=to;
		return ;
	}
	int mid=(l+r)>>1;
	updata(l,mid,ls,sa,to);updata(mid+1,r,rs,sa,to);
	upd(node);
}
ld query(int l,int r,int node,int sa,int se){
	if(l>se || r<sa)return inf;
	if(sa<=l && r<=se)return Tree[node];
	int mid=(l+r)>>1;
	ld q1=query(l,mid,ls,sa,se),q2=query(mid+1,r,rs,sa,se);
	upd(node);
	return Min(q1,q2);
}
void work()
{
	scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
	scanf("%d",&m);
	if(xl>xr){
		swap(xl,xr);swap(yl,yr);
	}
	a[++n].x=xl;a[n].y=yl;
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(x>=xl && x<=xr && y>=Min(yl,yr) && y<=Max(yl,yr)){
			a[++n].x=x;a[n].y=y;
		}
	}
	a[++n].x=xr;a[n].y=yr;
	int num=0;
	for(int i=1;i<=n;i++){
		b[++num]=a[i].y;
	}
	sort(b+1,b+num+1);
	int tot=unique(b+1,b+num+1)-b-1;
	for(int i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+tot+1,a[i].y)-b;
	sort(a+1,a+n+1);
	if(yl<=yr){
		for(int i=1;i<=n;i++)f[i]=inf;
		ld ans=100*fabs(yr-yl)+100*fabs(xr-xl);ld tmp;
		updata(1,n,1,1,0);
		for(int i=2;i<n;i++){
			tmp=query(1,n,1,1,a[i].y-1)+p1-20.0;
			if(tmp<f[i])f[i]=tmp;
			tmp=query(1,n,1,a[i].y,a[i].y)+p2-20.0;
			if(tmp<f[i])f[i]=tmp;
			updata(1,n,1,a[i].y,f[i]);
		}
		for(int i=2;i<=n;i++){
			if(a[n].y>=a[i].y)
				f[n]=min(f[n],f[i]);
		}
		if(n>2)ans+=f[n];
		printf("%.16Lf\n",ans);
	}
	else{
		for(int i=1;i<=n;i++)f[i]=inf;
		ld ans=100*fabs(yr-yl)+100*fabs(xr-xl);ld tmp;
		updata(1,n,1,1,0);
		for(int i=2;i<n;i++){
			tmp=query(1,n,1,a[i].y+1,n)+p1-20.0;
			if(tmp<f[i])f[i]=tmp;
			tmp=query(1,n,1,a[i].y,a[i].y)+p2-20.0;
			if(tmp<f[i])f[i]=tmp;
			updata(1,n,1,a[i].y,f[i]);
		}
		for(int i=2;i<=n;i++){
			if(a[n].y<=a[i].y)
				f[n]=min(f[n],f[i]);
		}
		if(n>2)ans+=f[n];
		printf("%.16Lf\n",ans);
	}
}

int main()
{
	work();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void work()’:
./Main.cpp:50:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
                                   ^
./Main.cpp:51:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
./Main.cpp:58:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

Judge Result