SGU 278 求调。
  • 板块学术版
  • 楼主SFlyer
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/14 18:30
  • 上次更新2024/7/14 19:10:13
查看原帖
SGU 278 求调。
489890
SFlyer楼主2024/7/14 18:30
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = double;

const int N = 1e5+5;

struct node {
	ld x,y;
	node operator - (const node &a) const {
		return node{x-a.x,y-a.y};
	}
	node operator + (const node &a) const {
		return node{x+a.x,y+a.y};
	}
	node operator * (const ld &a) const {
		return node{x*a,y*a};
	}
	ld operator ^ (const node &a) const {
		return x*a.y-y*a.x;
	}
	ld operator * (const node &a) const {
		return x*a.x+y*a.y;
	}
	ld len(){
		assert(!(x==0 && y==0));
		return sqrt(x*x+y*y);
	}
} p[N];

int n,st[N],top,ss[N];
ld ans;

#define sq(x) ((x)*(x)) 
#define inf 123456789

bool cmp(const node &a,const node &b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}

ld dis(int x,int y){
	return sqrt(sq(p[x].x-p[y].x)+sq(p[x].y-p[y].y));
}

ld K(int x,int y){
	return p[x].x==p[y].x?inf:(p[x].y-p[y].y)/(p[x].x-p[y].x);
}

int A,B;

bool crs(const node &a,const node &b,const node &c,const node &d){
	return ((c-a)^(b-a))*((d-a)^(b-a))<=0 && ((b-c)^(d-c))*((a-c)^(d-c))<=0;
}

node inter(const node &a,const node &b,const node &c,const node &d){
	node p=b-a,q=d-c,w=a-c;
	ld k=(w^q)/(q^p);
	assert((q^p)!=0);
	return a+p*k;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>A>>B;
//	n=75000,A=1000,B=1000;
	for (int i=1; i<=n; i++){
		ld a,b,c;
		cin>>a>>b>>c;
		//a=100,b=200,c=100;
		p[i]=node{a/c,b/c};
		ans=max(ans,min(A/p[i].x,B/p[i].y));
	}
	sort(p+1,p+1+n,cmp);
	int tp=0;
	for (int i=1; i<=n; i++){
		st[++top]=i;
		while (top>2 && K(st[top],st[top-2])<K(st[top-1],st[top-2])){
			st[top-1]=st[top];
			top--;
		}
	}
	for (int i=1; i<=top; i++){
		ss[++tp]=st[i];
	}
	top=0;
	for (int i=n; i; i--){
		st[++top]=i;
		while (top>2 && K(st[top],st[top-2])<K(st[top-1],st[top-2])){
			st[top-1]=st[top];
			top--;
		}
	}
	for (int i=1; i<=top; i++){
		ss[++tp]=st[i];
		assert(tp<N);
	}
	ss[0]=ss[tp];
	node o=node{0,0};
	node T=node{A,B};
	for (int i=0; i<tp; i++){
	//	cout<<ss[i]<<endl;
		if (ss[i]!=ss[i+1] && crs(p[ss[i]],p[ss[i+1]],o,T)){
			ans=max(ans,T.len()/inter(p[ss[i]],p[ss[i+1]],o,T).len());
		}
	}
	cout<<fixed<<setprecision(6)<<ans<<"\n";
	return 0;
}

不知道为啥 tle on #5。

2024/7/14 18:30
加载中...