半平面交求调
查看原帖
半平面交求调
94475
锦依卫小生楼主2024/8/23 21:38

思路:所以选手的时间可以写成 y=kx+by=kx+b x在这里代表骑行路程。不妨第一名看成是 −y-y 构成半平面交。求出半平面交的边后,找到由 nn 的边,若不是重边,则求出其相邻两条边的交点,以该交点更新答案;否则为并列,更新答案。

#include<bits/stdc++.h>
using namespace std;
const double INF=1E18;
const double pi=acos(-1.0);
const double eps=1e-10;
const int MAX=100+5;
vector<int>g[MAX];
int sgn(double x){
	if(fabs(x)<eps)
		return 0;
	else
		return x<0?-1:1;
}
struct Point{
	double x,y;
	int l1,l2;
	Point(){};
	Point(double x,double y):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator * (double k){return Point(x*k,y*k);}
};
typedef Point Vector;
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;};
struct Line{
	Point p;
	Vector v;
	double ang;
	int co;
	Line(){};
	Line(Point p,Vector v,int co):p(p),v(v),co(co){ang=atan2(v.y,v.x);}
	bool operator <(Line &L){return ang<L.ang||sgn(ang-L.ang)==0&&p.y<L.p.y;} 
};
bool OnLeft(Line L,Point p){return sgn(Cross(L.v,p-L.p))>=0;}
Point Cross_point(Line a,Line b){
	Vector u=a.p-b.p;
	double t=Cross(b.v,u)/Cross(a.v,b.v);
	return a.p+a.v*t;
}
vector<int> HPI(vector<Line>L){
	int n=L.size();
//	sort(L.begin(),L.end());
	int first,last;
	vector<Point> p(n);
	vector<Line> q(n);
	vector<int> ans;
	q[first=last=0]=L[0];
	for(int i=1;i<=n-1;++i){
		while(first<last&&!OnLeft(L[i],p[last-1])) last--;
		while(first<last&&!OnLeft(L[i],p[first])) first++;
		q[++last]=L[i];
		if(fabs(Cross(q[last].v,q[last-1].v))<eps){
			last--;
			if(OnLeft(q[last],L[i].p)) q[last]=L[i];
		}
		if(first<last)
			p[last-1]=Cross_point(q[last-1],q[last]); 
	}
	while(first<last&&!OnLeft(q[first],p[last-1])) last--;
	for(int i=first;i<=last;++i)
		ans.push_back(q[i].co);
	return ans;
}
double a[MAX],b[MAX],s;
int main(){
	int n;
	cin>>s>>n;
	vector<Line> L;
	vector<Line> tempL;
	tempL.push_back(Line(Point(0,0),Vector(0,-1),0));
	tempL.push_back(Line(Point(0,INF),Vector(-1,0),n+1));
	for(int i=1;i<=n;++i)
		scanf("%lf%lf",a+i,b+i);
	
	for(int i=1;i<=n;++i){
		tempL.push_back(Line(Point(0,-s/b[i]),Vector(1,-1/a[i]+1/b[i]),i));
	}
	sort(tempL.begin(),tempL.end());
	L.push_back(Line(tempL[0].p,tempL[0].v,0));
	int t=0;
	g[t].push_back(tempL[0].co);
	for(int i=1;i<=n+1;++i){
		if(sgn(tempL[i].ang-L[t].ang)==0&&sgn(tempL[i].p.y-L[t].p.y)==0){
			g[t].push_back(tempL[i].co);
		}
		else{
			t++;
			g[t].push_back(tempL[i].co);
			L.push_back(Line(tempL[i].p,tempL[i].v,t));
		}
	}
	vector<int> ans=HPI(L);
	double anst;
	double ansx=-INF;
	double 	tmin=INF;
	for(int i=1;i<=n-1;++i){
		tmin=min(tmin,s/b[i]); 
	}
	if(tmin-s/b[n]>ansx){
		ansx=tmin-s/b[n];
		anst=0;
	}
	for(int i=1;i<(int)ans.size()-1;++i){
		bool flag=0;
		for(int j=0;j<g[ans[i]].size();++j){
			if(g[ans[i]][j]==n){
				flag=1;
				break;
			}
		}	
		if(flag){
			Point p=Cross_point(L[ans[i-1]],L[ans[i+1]]);
			if(g[ans[i]].size()==1){		
				if(p.x<s){
					if(ansx<-p.x/a[n]-(s-p.x)/b[n]-p.y){
						ansx=-p.x/a[n]-(s-p.x)/b[n]-p.y;
						anst=p.x;
					}
				}
			}
			else{
				if(p.x<s){
					if(ansx<0){
						ansx=0;
						anst=p.x;
					} 
				}
			}
		}
	}
	tmin=INF;
	for(int i=1;i<=n-1;++i){
		tmin=min(tmin,s/a[i]); 
	}
	if(tmin-s/a[n]>ansx){
		ansx=tmin-s/a[n];
		anst=s;
	}
	if(ansx>0||sgn(ansx)==0){
		cout<<fixed<<setprecision(2)<<anst<<" "<<fixed<<setprecision(2)<<s-anst<<" "<<fixed<<setprecision(0)<<ansx*3600<<endl;
	}
	else{
		cout<<"NO";
	}
} 
2024/8/23 21:38
加载中...