记录编号	528099	评测结果	AAAAA
题目名称	解多项式方程	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2019-02-27 11:15:48	内存使用	3.16 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#include<iomanip>
using namespace std;
typedef long double ld;
const int tim=10000;
const ld eps=1e-15;
ld rando(ld l,ld r){
    int x,y;
    x=l*100;y=r*100;
	return ld(x+rand()%(y-x+1))/100.0;
}
void Print(ld x,int y){cout<<setprecision(y) <<std::fixed <<x<<' ';}
class point{
	public:
		ld A;
		int B;
		void print(int x){
			Print(A,x);
			Print(B,x);
			cout<<endl;
		}
		point operator +(point a){
			point b;
			if(B!=a.B)cout<<"Warning"<<endl;
			b.B=B;
			b.A=A+a.A;
			return b;
		}
		point operator -(point a){
			point b;
			if(B!=a.B)cout<<"Warning"<<endl;
			b.B=B;
			b.A=A-a.A;
			return b;
		}
		point operator *(point a){
			point b;
			b.B=B+a.B;
			b.A=A*a.A;
			return b;
		}
		point operator /(point a){
			point b;
			b.B=B-a.B;
			b.A=A/a.A;
			return b;
		}
		inline ld val(ld x){return A*pow(x,B);}
};
bool operator <(point a,point b){
	if(a.B==b.B)return a.A<b.A;
	return a.B<b.B;
}
point make(ld x,int y){
	point a;
	a.A=x;
	a.B=y;
	return a;
}
point inv(point a){a.A=1/a.A;a.B=-a.B;return a;}
class polynomial {
	public:
		vector<point> S;
		void print(int x){for(int i=0;i<S.size();i++)S[i].print(x);}
		inline void add(point x){S.push_back(x);}
	    inline void update(){
	    	sort(S.begin(),S.end());
	    	vector<point> T;
	    	point u,v;ld KMP=0;KMP=S[0].A;
	    	for(int i=0;i<S.size();i++){
	    		if(i==S.size()-1){
	    			T.push_back(make(KMP,S[i].B));
	    			continue;
	    		}
	    		u=S[i];v=S[i+1];
	    		if(u.B==v.B)KMP+=v.A;
	    		else{
	    			T.push_back(make(KMP,u.B));
	    			KMP=v.A;
	    		}
	    	}
	    	S=T;
	    }
	    ld val(ld x){
	    	ld sum=0;
	    	for(int i=0;i<S.size();i++)sum=sum+S[i].val(x);
	    	return sum;
	    }
	    void FFT(){
	    	vector<point> T;
	    	point u;
	    	for(int i=0;i<S.size();i++){
	    		u=S[i];
	    	    if(u.B==0)continue;
	    	    u.A*=u.B;
	    	    u.B--;
	    	    T.push_back(u);
	    	}
	    	S=T;
	    }
	    void DFT(){
			vector<point> T;
	    	point u;
	    	for(int i=0;i<S.size();i++){
	    		u=S[i];
	    	    if(u.B==-1)continue;
	    	    u.B++;
	    	    u.A/=u.B;
	    	    T.push_back(u);
	    	}
	    	S=T;
	    }
	    ld findroot(ld y){
	    	polynomial T;
	    	vector<point > H;
	    	H=S;
	    	add(make(-y,0));
	    	update();
            T.S=S;
	    	FFT();
	    	ld x=rando(0.0,1001.0),newx;
	    	for(int i=1;i<=tim;i++)x=x-T.val(x)/val(x); 
	    	S=H;
	    	return x;
	    }
};
int main(){
	freopen("equationsolve.in","r",stdin);
	freopen("equationsolve.out","w",stdout);
	srand(time(NULL));
	int i,n;
	ld x,y,ans=0,sum=0;
	polynomial Q;
    cin>>n;
    for(i=1;i<=n;i++){cin>>x>>y;Q.add(make(x,y));}
    ans=Q.findroot(0);
    Print(ans,18);
	return 0;
}