70 pts 求调
查看原帖
70 pts 求调
684245
zhangyaiwei楼主2024/8/17 23:53

#5 WA

#6,#13,#14,#15 TLE

#include<bits/stdc++.h>
using namespace std;
const long double Eps=1e-15,Inf=1e10;
long long X[111111],x[111111];
int n,ans,y[111111],Y[111111];
struct Nd{
	long double x,y;
};
inline bool ONL(Nd o,Nd a,Nd b){
	return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x)<0;
}
struct Sg{
	long double X1,Y1,X2,Y2,A;
	Sg(long double X1_,long double Y1_,long double X2_,long double Y2_){
		X1=X1_,Y1=Y1_,X2=X2_,Y2=Y2_;
		Init_GTA();
	}
	inline Nd operator & (const Sg &s)const{
		long double A=(s.X2-X1)*(Y2-Y1)-(s.Y2-Y1)*(X2-X1),B=(s.X1-X1)*(Y2-Y1)-(s.Y1-Y1)*(X2-X1);
		return {(A*s.X1-B*s.X2)/(A-B),(A*s.Y1-B*s.Y2)/(A-B)};
	}
	inline void Init_GTA(){
		A=atan2(Y2-Y1,X2-X1);
	}
	inline long double GTA(){//Get The Angle
		Init_GTA();
		return A;
	}
	inline friend bool operator < (Sg a,Sg b){
		long double Aa=a.GTA(),Ab=b.GTA();
		if(fabs(Aa-Ab)<Eps) return ONL({a.X1,a.Y1},{a.X2,a.Y2},{b.X1,b.Y1});
		return Aa<Ab;
	}
};
vector<pair<Sg,int> > v;
vector<Sg> vg;
deque<Sg> d;
void PRINT(deque<Sg> D){
	cout<<"S\n";
	while(!D.empty()){
		Sg Fr=D.front();
		D.pop_front();
		cout<<Fr.X1<<","<<Fr.Y1<<" "<<Fr.X2<<","<<Fr.Y2<<endl;
	}
	cout<<"E\n";
}
void PRINT2(deque<Sg> D){
	while(D.size()>1){
		Sg S1=D.front();
		D.pop_front();
		Sg S2=D.front();
		cout<<"("<<(S1&S2).x<<","<<(S1&S2).y<<")";
	}
	cout<<endl;
}
bool C(int I){
	d.clear(),vg.clear();
	for(int i=0;i<v.size();i++){
		if(v[i].second<=I){
			vg.push_back(v[i].first);
		}
	}
	for(int i=0;i<vg.size();i++){
		if(i<1||fabs(vg[i-1].GTA()-vg[i].GTA())>Eps){
			while(d.size()>1){
				Sg S1=d.back();
				d.pop_back();
				Sg S2=d.back();
				if(!ONL({vg[i].X1,vg[i].Y1},{vg[i].X2,vg[i].Y2},S1&S2)){
					d.push_back(S1);
					break;
				}
			}
			while(d.size()>1){
				Sg S1=d.front();
				d.pop_front();
				Sg S2=d.front();
				if(!ONL({vg[i].X1,vg[i].Y1},{vg[i].X2,vg[i].Y2},S1&S2)){
					d.push_front(S1);
					break;
				}
			}
			d.push_back(vg[i]);
			// PRINT(d);
			// PRINT2(d);
		}
		else{
			// cout<<vg[i].X1<<","<<vg[i].Y1<<" "<<vg[i].X2<<","<<vg[i].Y2<<" NONE\n";
		}
	}
	Sg Fr=d.front();
	while(d.size()>1){
		Sg S1=d.back();
		d.pop_back();
		Sg S2=d.back();
		if(!ONL({Fr.X1,Fr.Y1},{Fr.X2,Fr.Y2},S1&S2)){
			d.push_back(S1);
			break;
		}
	}
	return d.size()>2;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>Y[i];
		X[i]=x[i]*x[i];
		y[i]-=Eps,Y[i]+=Eps;
	}
	for(int i=1;i<=n;i++){
		v.push_back(make_pair(Sg(-(long double)y[i]/X[i],0,0,(long double)y[i]/x[i]),i));
		v.push_back(make_pair(Sg(0,(long double)Y[i]/x[i],-(long double)Y[i]/X[i],0),i));
	}
	/*
	(eps,inf) (inf,inf)
	(eps,eps) (inf,eps)
	*/
	v.push_back(make_pair(Sg(-Eps,1,-Eps,-Eps),0));
	v.push_back(make_pair(Sg(-Eps,-Eps,1,-Eps),0));
	v.push_back(make_pair(Sg(Inf,-Eps,Inf,1),0));
	v.push_back(make_pair(Sg(1,Inf,-Eps,Inf),0));
	sort(v.begin(),v.end());
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)/2;
		if(C(mid)){
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	cout<<(C(l)?l:ans);
}
2024/8/17 23:53
加载中...