Submission #2291892

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#define pi 3.14159265358979343846
using namespace std;
struct N{
	int x,y;
}s,t,f[200005];
int n,start,endd,opt[200005],k,opt_n,flag;
double ans;
bool comp(N a,N b){return a.x<b.x;}
int search(int h){
    int l=1,mid,r=opt_n;
    while(l<=r){
        mid=(l+r)/2;
        if(opt[mid]>=h)
            if(mid+1<=r&&opt[mid+1]>=h) l=mid+1;
            else return(mid);
        else r=mid-1; 
    }
    return r;
}
int main(){
	scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d%d",&f[i].x,&f[i].y);
	sort(f+1,f+n+1,comp);
	//for(int i=1;i<=n;++i) printf("%d %d\n",f[i].x,f[i].y);
	if(s.x>t.x){
		int temp=s.x;
		s.x=t.x;
		t.x=temp;
	}
	if(t.y>s.y) flag=-1;
	else flag=1;
	for(int i=1;i<=n;++i){
		if(f[i].x>s.x&&(i-1<1||f[i-1].x<=s.x)&&flag*s.y>=flag*f[i].y&&flag*t.y<=flag*f[i].y) start=i;
		if(f[i].x<t.x&&(i+1>n||f[i+1].x>=t.x)&&flag*s.y>=flag*f[i].y&&flag*t.y<=flag*f[i].y) endd=i;
	}
	if(start==0&&endd==0&&s.x!=t.x){
		printf("%.15lf",(double)100*(t.x-s.x)+100*(-flag*(t.y-s.y)));
		return 0;
	}
	
	opt[1]=flag*f[start].y; opt_n=1;
	//printf("%d\n",flag);
    for(int i=start+1;i<=endd;++i){
        int h=flag*f[i].y;
        if(flag*t.y-h>0) continue;
        if(h<opt[opt_n]) k=++opt_n;
        else k=search(h)+1;
        //printf("%d\n",k);
        opt[k]=h;
    }
	if(s.x==t.x){
		int cnt=0;
		for(int i=1;i<=n;++i)
			if(f[i].x==s.x)
				cnt++;
		printf("%.15lf",100*(-flag*t.y-s.y)-20*cnt+10*pi*cnt);
		return 0;
	}
	if(s.y==t.y){
		int cnt=0;
		for(int i=1;i<=n;++i)
			if(f[i].x>s.x&&f[i].x<t.x&&f[i].y==s.y)
				cnt++;
		printf("%.15lf",100*(t.x-s.x)-20*cnt+10*pi*cnt);
		return 0;
	}
    //printf("%d %d %d\n",start,end,opt_n);
    printf("%.15lf",100*(t.x-s.x)+100*(-flag*(t.y-s.y))-opt_n*20+opt_n*pi*5);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:23:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);
                                       ^
./Main.cpp:24:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:25:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;++i) scanf("%d%d",&f[i].x,&f[i].y);
                                                     ^

Judge Result