Language: C++


#include <bits/stdc++.h>

using namespace std;

#define fill(a,val) memset(a, (val), sizeof a)
#define pb push_back
#define lli long long int
#define scantype int
#define endl "\n"
#define unique(x) x.erase(unique(x.begin(),x.end()), x.end())

lli MOD  = 1000000007;
lli inf = 1e15;

void scan(scantype &x);
lli powermod(lli _a,lli _b,lli _m){lli _r=1;while(_b){if(_b%2==1)_r=(_r*_a)%_m;_b/=2;_a=(_a*_a)%_m;}return _r;}
lli string_to_number(string s){lli x=0; stringstream convert(s); convert>>x; return x;}
lli add(lli a,lli b){lli x = (a+b)%MOD; return x; }
lli mul(lli a,lli b){lli x = (a*b)%MOD; return x; }
lli sub(lli a,lli b){lli x = (a-b+MOD)%MOD; return x; }
lli divi(lli a,lli b){lli x = a;lli y = powermod(b,MOD-2,MOD);lli res = (x*y)%MOD;return res;}

#define N 200003

double PI = 3.141592653589793238462643383,R=10.0;

map<int,int> actual;

struct Fpos{
	int x,y,totFountain,id;
	Fpos(int x,int y,int totFountain) {
		this->x = x;
		this->y = y;
		this->totFountain = totFountain;
	}
	Fpos(int x,int y,int totFountain,int id) {
		this->x = x;
		this->y = y;
		this->totFountain = totFountain;
		this->id = id;
	}
	Fpos() {
		this->x = -1;
		this->y = -1;
		this->totFountain = 0;
	}
};

struct SegmentTree{
	typedef Fpos stt; //change data type here
	static const int MAXN = 4*N;
	stt tree[MAXN];

	stt merge(stt l,stt r)
	{
		if(l.totFountain < r.totFountain) return r;
		return l;
	}
	void build(int node,int start,int endd)
	{
		if(start==endd)
		{
			tree[node] = Fpos(-1,-1,0,start);
			return;
		}

		int mid = (start+endd)>>1;

		build(node<<1,start,mid);
		build((node<<1) + 1,mid+1,endd);

		tree[node] = merge(tree[node<<1],tree[(node<<1)+1]);
	}

	void update(int node,int start,int endd,int idx,stt val)
	{
		if(start==endd)
		{
			tree[node] = val; //increase value type update
			return;
		}

		int mid = (start+endd)>>1;

		if(idx<=mid)
			update(node<<1,start,mid,idx,val);
		else
			update((node<<1)+1,mid+1,endd,idx,val);

		tree[node] = merge(tree[node<<1],tree[(node<<1)+1]);
	}

	stt read(int node,int start,int endd,int l,int r)
	{
		if(start==l && endd==r)
			return tree[node];

		int mid = (start+endd)>>1;

		if(r<=mid)
			return read(node<<1,start,mid,l,r);
		if(l>mid)
			return read((node<<1)+1,mid+1,endd,l,r);

		return merge(read(node<<1,start,mid,l,mid),read((node<<1)+1,mid+1,endd,mid+1,r));
	}
}seg_tree;


struct Fountain{
	int x,y;
	Fountain(int x,int y){
		this->x = x;
		this->y = y;
	}
	bool operator<(const Fountain& a){
		return tie(x,y) < tie(a.x,a.y);
	}
};

bool inRange(int x,int y,int x1,int y1,int x2,int y2){
	if(y1 < y2){
		if(x>=x1 && x<=x2 && y>=y1 && y<=y2) return true;
	} else {
		if(x>=x1 && x<=x2 && y>=y2 && y<=y1) return true;
	}
	return false;
}

void compressNumber(vector<Fountain>& vp){
	vector<int> tmp;
	for(auto it : vp) tmp.pb(it.y);
	sort(tmp.begin(),tmp.end());
	for(int i=1;i<=tmp.size();i++){
		actual[tmp[i-1]] = i;
	}
}

int main(void)
{
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;

  if(x1>x2){
  	swap(x1,x2);
  	swap(y1,y2);
  }

  int n;
  cin>>n;

  vector<Fountain> vp;
  vp.pb(Fountain(x1,y1));

  for(int i=0;i<n;i++) {
  	int x,y;
  	scan(x);scan(y);
  	if(inRange(x,y,x1,y1,x2,y2))
  		vp.pb(Fountain(x,y));
  }

  sort(vp.begin() ,vp.end());

  compressNumber(vp);

  int maxFountain = 0 , MX = N-1;

  seg_tree.build(1,1,MX);

  Fpos parent[N];

  for(int i=vp.size()-1;i>=0;i--) {
  		int idx = actual[vp[i].y];
  		Fpos fp;

  		if(y1 < y2) {
  			fp = seg_tree.read(1,1,MX,idx,MX);
  		} else {
  			fp = seg_tree.read(1,1,MX,1,idx);
  		}

  		//cerr<<"Curr: "<<vp[i].x<<" "<<vp[i].y<<" "<<fp.x<<" "<<fp.y<<" "<<fp.totFountain<<endl;
  		parent[i] = fp;
  		seg_tree.update(1,1,MX,idx,Fpos(vp[i].x,vp[i].y,1+fp.totFountain,i));
  }

  double res = 0;

  int currIdx = 0,foutainInPath = -1,flag=0;

  while(1){
  	Fpos nextPar = parent[currIdx];
  	foutainInPath++;

  	double dx = abs(nextPar.x - vp[currIdx].x);
  	double dy = abs(nextPar.y - vp[currIdx].y);
  	double dist = 0;

  	if(nextPar.x == -1) {
  		dx = abs(x2 - vp[currIdx].x);
  		dy = abs(y2 - vp[currIdx].y);
  		if(x2 == vp[currIdx].x || y2 == vp[currIdx].y)
  			flag = 1;
  	}
  	
  	dist += (dx+dy)*100;
  	
  	//cerr<<vp[currIdx].x<<","<<vp[currIdx].y<<" ---> "<<nextPar.x<<" "<<nextPar.y<<" "<<dist<<endl;
  	res += dist;
  	if(nextPar.x == -1) break;
  	currIdx = nextPar.id;
  }

  if(foutainInPath == 0) {
  	cout<<res;
  	return 0;
  }

  double delta = R*2.0 - ((PI * R) / (double)2.0);
  
  if(totFountain == min(abs(x1-x2),abs(y1-y2)) + 1) {
  	res += (PI-(double)2)*R;
  	foutainInPath--;
  }

  res -= delta * foutainInPath;
  cout<<setprecision(15)<<res;
  return 0;
}


void scan(scantype &x)
{
    register int c = getchar(); //for negative/positive
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = getchar());
    if(c=='-') {neg=1;c=getchar();}
    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:222:6: error: 'totFountain' was not declared in this scope; did you mean 'maxFountain'?
  222 |   if(totFountain == min(abs(x1-x2),abs(y1-y2)) + 1) {
      |      ^~~~~~~~~~~
      |      maxFountain
a.cc: In function 'void scan(int&)':
a.cc:235:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  235 |     register int c = getchar(); //for negative/positive
      |                  ^