记录编号	274735	评测结果	AAAAA
题目名称	解多项式方程	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-06-29 15:46:31	内存使用	0.31 MiB

#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <ctime>
using namespace std;
ifstream cin("equationsolve.in");
ofstream cout("equationsolve.out");
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)//寻找一个x,使得f(x)=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;
	    }
	   
};
void test()
{
	int i,n;
	ld x,y;
	ld 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(eps,18);
    Print(ans,18);
}
int main()
{
	srand(time(NULL));
	test();
	return 0;
}