10pts求助
查看原帖
10pts求助
367387
cainiaoshanglu楼主2022/5/26 22:09

貌似问题都处在小数点后,可能是啥奇怪的精度问题

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#define int long long
#define double long double
using namespace std;

void read(int &x){
	x=0;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
}
struct Vector{
	double x,y,cs;
	Vector(){}
	Vector(double xx,double yy){
		x=xx;
		y=yy;
	}
	void show(){
		printf("(%lf %lf)",x,y);
	}
	double len(){
		return sqrt(x*x+y*y);
	}
	friend Vector operator-(Vector a,Vector b){
		return Vector(a.x-b.x,a.y-b.y);
	}
	friend double operator*(Vector a,Vector b){
		return a.x*b.x+a.y*b.y;
	}
	friend double operator^(Vector a,Vector b){
		return a.x*b.y-a.y*b.x;
	}
	friend bool operator<(Vector a,Vector b){
		if(a.cs==b.cs){
			return a.len()>b.len();
		}
		return a.cs>b.cs;
	}
} a[200010];
set<Vector> st;
int n,tp=0;
double res=0;
void add(Vector v){
	v.cs=(v*Vector(1,0))/v.len();
	auto it=st.insert(v).first;
	auto l=it,r=it;
	l--;
	r++;
	res+=((*l)-(*it)).len()+((*r)-(*it)).len()-((*l)-(*r)).len();
	{
	auto i=it,j=i--,k=j--;
	i--;
	for(;j!=st.begin() && ((*k-*i)^(*j-*i))>0;){
		res-=(*k-*j).len()+(*j-*i).len()-(*k-*i).len();
		st.erase(j);
		j=i--;
	}
	}
	it=st.find(v);
	it++; 
	{
	auto i=it,j=i--,k=j--;
	i--;
	for(;j!=st.begin() && ((*k-*i)^(*j-*i))>0;){
		res-=(*k-*j).len()+(*j-*i).len()-(*k-*i).len();
		st.erase(j);
		j=i--;
	}
	}
	die:;
}
bool is[200010]={0};
int qs[200010]={0};
double ans[200010];
signed main(){
	read(n);
	res=n;
	Vector cur,null=Vector(0,0),edge=Vector(n,0);
	scanf("%Lf %Lf",&cur.x,&cur.y);
	null.cs=-1;
	edge.cs=1;
	st.insert(null);
	st.insert(edge);
	add(cur);
	int m,q;
	read(m);
	for(int i=1;i<=m;i++){
		scanf("%Lf %Lf",&a[i].x,&a[i].y);
	}
	read(q);
	int tmp;
	for(int i=1;i<=q;i++){
		read(tmp);
		if(tmp==1){
			read(qs[i]);
			is[qs[i]]=true;
		}
	}
	for(int i=1;i<=m;i++){
		if(!is[i]){
			add(a[i]);
		}
	}
	for(int i=q;i;i--){
		if(qs[i]){
			add(a[qs[i]]);
		}else{
			ans[i]=res;
		}
	}
	for(int i=1;i<=q;i++){
		if(!qs[i]){
			printf("%.2Lf\n",ans[i]);
		}
	}
	return 0;
}
2022/5/26 22:09
加载中...