求助!
查看原帖
求助!
369181
bamboo12345楼主2023/7/23 11:22

rt,卡在 subtask_1_02 那一个也仅是那一个点,求调

#include <bits/stdc++.h>
#define int long long
#define Pi M_PI
using namespace std;
const int maxn=2e5+5;
int sx,sy,ex,ey;
struct node
{
	int x,y;
	friend bool operator<(node x,node y)
	{
		return x.x<y.x;
	}
} p[maxn];
int n,tot,len,x[maxn];
signed main()
{
	cin >>sx>>sy>>ex>>ey>>n;
	if(sx>ex)
		swap(sx,ex),swap(sy,ey);
	for(int i=1;i<=n;i++)
	{
		cin >>p[i].x>>p[i].y;
		if((p[i].x<=ex&&p[i].x>=sx&&p[i].y>=min(sy,ey)&&p[i].y<=max(sy,ey)))
			p[++tot]=p[i];
	}
	n=tot;
	sort(p+1,p+n+1);
	if(sx==ex&&sy==ey)
	{
		cout <<0<<endl;
		return 0;
	}
	if(sy<ey)
	{
		for(int i=1;i<=n;i++)
		{
			if(p[i].y>x[len])
				x[++len]=p[i].y;
			else
				x[lower_bound(x+1,x+len+1,p[i].y)-x]=p[i].y;
		}
	//	cout <<len<<endl;
		if(len==min(ex-sx+1,ey-sy+1))
			printf("%.20lf",100.0*(ex-sx+ey-sy)+((double)(len)-1)*(M_PI*5-20)+(M_PI*10-20));
		else
			printf("%.20lf",100.0*(ex-sx+ey-sy)+len*(Pi*5-20));
	}
	else
	{
		for(int i=n;i>=1;i--)
		{
			if(p[i].y>x[len])
				x[++len]=p[i].y;
			else
				x[lower_bound(x+1,x+len+1,p[i].y)-x]=p[i].y;
		}
		if(len==min(ex-sx+1,sy-ey+1))
			printf("%.20lf",100.0*(ex-sx+sy-ey)+((double)(len)-1)*(Pi*5-20)+(Pi*10-20));
		else
			printf("%.20lf",100.0*(ex-sx+sy-ey)+len*(Pi*5-20));
	}
	return 0;
}
/*
3 3 1 1
2
1 3
3 2
*/
2023/7/23 11:22
加载中...