大国工匠之eps调精度
查看原帖
大国工匠之eps调精度
198964
Msents楼主2023/8/18 20:30

-1e9wa一个点,-1e8wa另外八个点

-2e9wa四个点

-1.5e9才ac

btw?


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int MaxN=1000;
const double Minu=0.0000000015;
struct Line{
	Line(){}
	Line(const int x1,const int y1,const int x2,const int y2,const int w)
		:x1(x1),y1(y1),x2(x2),y2(y2),w(w){}
	double k()const{
		if(x1-x2==0)return 1e12;
		return ((double)y1-y2)/(x1-x2);
	}
	pair<double,double>mid()const{return make_pair((x1+x2)/2.0,(y1+y2)/2.0);}
	double li()const{
		if(k()==0)return mid().first+1e15;
		return mid().second+mid().first*(1/k());
	}
	int x1,y1,x2,y2;
	int w;
};
vector<Line>v;
int n;
pair<int,int>p[MaxN+1];
int w[MaxN+1];
void Solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y>>w[i];
		p[i]=make_pair(x,y);
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			v.emplace_back(
				p[i].first,
				p[i].second,
				p[j].first,
				p[j].second,
				w[i]+w[j]
			);
	sort(v.begin(),v.end(),
		[](const Line&a,const Line&b)->bool{
			if(abs(a.k()-b.k())<=Minu){
				if(abs(a.li()-b.li())<=Minu){
					return a.w>b.w;
				}else return a.li()<b.li();
			}else return a.k()<b.k();
		}
	);
	int ans=0;
	for(int i=0,j=i;i<v.size();i=++j){
		double k=v[i].k(),li=v[i].li();
		while(
			j+1<v.size()&&
			abs(v[j+1].k()-k)<=Minu&&
			abs(v[j+1].li()-li)<=Minu
		)j++;
		for(int p=i+1;p<=j;p++){
			if(
				v[i].x1+v[i].x2==v[p].x1+v[p].x2&&
				v[i].y1+v[i].y2==v[p].y1+v[p].y2
			)continue;
			ans=max(ans,v[i].w+v[p].w);
		}
	}
	if(!ans)cout<<-1;
	else cout<<ans;
}
#undef int
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solve();
	return 0;
}


2023/8/18 20:30
加载中...