Submission #7289954


Source Code Expand

Copy
#include <bits/stdc++.h>
#define elif else if
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;
#define llGeo
#define __baseInc__
#if defined intGeo
typedef int T;
const T inf=0x3fffffff;
#elif defined llGeo
typedef long long T;
const T inf=0x3fffffffffffffffLL;
#else
typedef double T;
const T inf=1/.0;
#endif

const double Pi=3.14159265358979323846;
double eps=1e-8;

struct vec;
typedef vec node;
struct line;
struct seg;
struct poly;
struct matx;
struct lns;

inline bool zero(int x){return x==0;}
inline bool zero(long long x){return x==0;}
inline bool zero(double x){return abs(x)<eps;}
inline bool zero(const vec&v);
inline int sign(T x){return zero(x)?0:(x>0?1:-1);}


double cos(const vec&p1,const vec&p2);
double sin(const vec&p1,const vec&p2);
double dist(const node&x,const node&y);
matx rotMtx(const double&deg);

struct vec{
	T x,y;
	//构造函数
	vec(T x=0,T y=0):x(x),y(y){}
	double abs()const{return sqrt((double)x*x+y*y);}
	double agl()const{return atan2(y,x);}
	vec e()const{double l=abs();return vec(x/l,y/l);}
	//向量基本操作
	bool operator==(const vec&p)const{return zero(*this-p);}
	bool operator!=(const vec&p)const{return !(*this==p);}
//	bool operator<(const vec&p)const{return agl()<p.agl();}
	vec operator+(const vec&p)const{return vec(x+p.x,y+p.y);}
	vec operator-(const vec&p)const{return vec(x-p.x,y-p.y);}
	vec operator*(const T&k)const{return vec(k*x,k*y);}//数乘
	vec operator-()const{return vec(-x,-y);}
	T operator*(const vec&p)const{return x*p.x+y*p.y;}//点乘
	T operator^(const vec&p)const{return x*p.y-y*p.x;}//叉乘
	double operator,(const vec&p)const{return acos(cos(*this,p));}//夹角
	bool operator||(const vec&p)const{return zero(*this^p);}//平行
	bool operator|(const vec&p)const{return zero(*this^p);}//共线
	bool operator&&(const vec&p)const{return !(*this||p);}//相交
	bool operator&(const vec&p)const{return zero(*this*p);}//垂直
	vec rota(const double&deg)const{double c=cos(deg),s=sin(deg);return vec(x*c-y*s,x*s+y*c);};//旋转
	
	//点扩展操作
	int operator%(const line&l)const;//点在哪边?
	node operator>>(const line&l)const;//投影
	bool on(const line&l)const;//点在直线上?
	bool on(const seg&s)const;//点在线段上?
	bool on(const poly&p)const;//点在折线上?
	bool in(const poly&p)const;//点在多边形内?
	
	void print()const{
		cout<<"("<<x<<','<<y<<")";
	}
	
};
inline bool zero(const vec&v){return zero(v.x)&&zero(v.y);}

struct line{
	vec dir;node pnt;
	line(){}
	line(const node&pnt,const vec&dir):dir(dir),pnt(pnt){}//点向式
//	line(const seg&s):dir(s.pnt1-s.pnt2),pnt(s.pnt1){}//线段拓展
	line(const T&x,const T&y):dir(vec(x,-y)),pnt(x,0){}//截距式

	bool operator||(const line&l)const{return (dir||l.dir)&&((pnt-l.pnt)&&dir);}//平行
	bool operator|(const line&l)const{return (dir||l.dir)&&((pnt-l.pnt)||dir);}//共线
	bool operator&&(const line&l)const{return dir&&l.dir;}//相交
	bool operator&(const line&l)const{return dir&l.dir;}//垂直
	node operator*(const line&l)const{
		double k=((pnt.y-l.pnt.y)*l.dir.x-(pnt.x-l.pnt.x)*l.dir.y)/double(dir^l.dir);
		return node(pnt.x+k*dir.x,pnt.y+k*dir.y);
	}//交点
	bool operator<(const line&l)const{
		double t1=this->dir.agl(),t2=l.dir.agl();
		return zero(t1-t2)?(this->pnt%l<=0):t1<t2;
	}//极角序偏序
	
	void print()const{
		cout<<"Agl:"<<fixed<<setprecision(4)<<dir.agl()<<" Pnt:";
		pnt.print();
	}
	
};

struct seg{
	node pnt1,pnt2;
	seg(){}
	seg(const node&p1,const node&p2):pnt1(p1),pnt2(p2){}
	operator line()const{return line(pnt1,pnt2-pnt1);}
	double len()const{return dist(pnt1,pnt2);}
	
	//线段之间关系
	bool operator||(const seg&s)const{return (line)*this||(line)s;}//平行
	bool operator|(const seg&s)const{return (line)*this|(line)s;}//共线
	bool operator&&(const seg&s)const{
		if(pnt1.on(s)||pnt2.on(s)||s.pnt1.on(*this)||s.pnt2.on(*this))return 1;
		line l1=(line)*this,l2=(line)s;
		if(l1.dir||l2.dir)return 0;
		else return (pnt1%l2)*(pnt2%l2)<=0 && (s.pnt1%l1)*(s.pnt2%l1)<=0;
	}//相交
	bool operator&(const seg&s)const{return (line)*this&(line)s;}//垂直
	
	//线段与直线的关系
	bool operator||(const line&s)const{return (line)*this||s;}//平行
	bool operator|(const line&s)const{return (line)*this|s;}//共线
	bool operator&&(const line&s)const{
		if(pnt1.on(s)||pnt2.on(s))return 1;
		line l=(line)*this;
		if(l.dir||s.dir)return 0;
		else return (pnt1%s)*(pnt2%s)<=0;
	}//相交
	bool operator&(const line&s)const{return (line)*this&s;}//垂直
	
	void print()const{
		cout<<'(';pnt1.print();cout<<',';pnt2.print();cout<<')';
	}

};

struct poly{
	vector<node>pnt;
	vector<seg>edge;
	poly(){}
	poly(const vector<node>&p){
		pnt=p;
		for(int i=1;i<pnt.size();i+=1)edge.push_back(seg(pnt[i-1],pnt[i]));
	}
	
	void init(const T&x){
		append(node(x,x)),append(node(-x,x)),append(node(-x,-x)),append(node(x,-x));
	}
	
	void append(const node&p){
		if(pnt.size())edge.push_back(seg(pnt.back(),p));
		pnt.push_back(p);
	}
	
	poly&toPoly();
	double len()const;
	T area()const;
	bool coll()const;//判断共线
	poly conHull()const;//凸包_Graham's Scan法
	poly AconHull()const;//凸包_Andrew算法
	void print()const{
		cout<<pnt.size();
		cout<<" Node: [";
		for(auto&p:pnt){
			p.print();
			cout<<',';
		}
		cout<<"\b]";
	}
	
};

struct lns{
	vector<line>lines;//有向直线
	lns(){}
	lns(const vector<line>&ls):lines(ls){}
	lns(const poly&pl){for(auto&e:pl.edge){lines.push_back((line)e);}}
	void init(const double&t){
		append(line(node(-t,-t),vec(1,0))),append(line(node(t,-t),vec(0,1))),
		append(line(node(t,t),vec(-1,0))),append(line(node(-t,t),vec(0,-1)));
	}
	void append(const line&l){lines.push_back(l);}
	vector<node>ihf();//半平面交
	void print()const{
		cout<<lines.size();
		cout<<" Line: {";
		for(auto&p:lines){
			cout<<'[';
			p.print();
			cout<<"],";
		}
		cout<<"\b}";
	}
};

inline double cos(const vec&p1,const vec&p2){return (p1*p2)/(p1.abs()*p2.abs());}
inline double sin(const vec&p1,const vec&p2){return (p1^p2)/(p1.abs()*p2.abs());}

inline double dist(const node&x,const node&y){return (x-y).abs();}
inline double dist(const node&x,const line&y){return abs(((x-y.pnt)^(y.dir))/y.dir.abs());}

inline int node::operator%(const line&l)const{return sign((*this-l.pnt)^l.dir);}
inline node node::operator>>(const line&l)const{return node(l.pnt)+l.dir*((l.dir*(*this-l.pnt))/double(l.dir*l.dir));}//投影

inline bool node::on(const line&l)const{return !(*this%l);}
inline bool node::on(const seg&s)const{
	T xm=min(s.pnt1.x,s.pnt2.x),xM=max(s.pnt1.x,s.pnt2.x), ym=min(s.pnt1.y,s.pnt2.y),yM=max(s.pnt1.y,s.pnt2.y);
	return on(line(s))&&xm<=x&&x<=xM&&ym<=y&&y<=yM;
}
bool node::on(const poly&p)const{
	for(auto&i:p.edge)if(on(i))return 1;
	return 0;
}
bool node::in(const poly&p)const{
	int t=0;
	if(on(p))return 1;
	for(auto&s:p.edge)
		if((s.pnt1.y>=y&&s.pnt2.y<y||s.pnt1.y<y&&s.pnt2.y>=y)&&(sign(s.pnt1.y-s.pnt2.y)*((s.pnt1.x-s.pnt2.x)*(y-s.pnt1.y)+(s.pnt1.x-x)*(s.pnt1.y-s.pnt2.y))>0))t=!t;
	return t;
}

//poly:
inline poly&poly::toPoly(){
	if(edge.size()<pnt.size())edge.push_back(seg(pnt.back(),pnt.front()));
	return *this;
}
	
double poly::len()const{
	double c=0;
	for(auto&i:edge)c+=i.len();
	return c;
}

T poly::area()const{
	T s=0;
	for(int i=2;i<pnt.size();++i)s+=(pnt[i]-pnt[0])^(pnt[i-1]-pnt[0]);
	return abs(s/2);
}

bool poly::coll()const{
	const node&st=pnt[0];
	vec dt;
	for(int i=1;i<pnt.size();i+=1){
		if(zero(dt)){
			dt=st-pnt[i];
		}
		else if(!(st-pnt[i]||dt))return 0;
	}
	return 1;
}

poly poly::conHull()const{
	if(pnt.empty())return*this;
	const node&st=*min_element(pnt.begin(),pnt.end(),[](const node&x,const node&y){return x.y<y.y||(zero(x.y-y.y)&&x.x<y.x);});
	vector<node>nds;
	for(auto&p:pnt)if(st!=p)nds.push_back(p);
	sort(nds.begin(),nds.end(),[st](const node&x,const node&y){return (x-st^y-st)>0||zero(x-st^y-st)&&((x-st).abs()<(y-st).abs());});
	vector<node>bag{st};
	for(auto&t:nds){
		if(t==bag.back())continue;
		while(bag.size()>1&&(((bag[bag.size()-1]-bag[bag.size()-2])^(t-bag[bag.size()-1]))<0||zero((bag[bag.size()-1]-bag[bag.size()-2])^(t-bag[bag.size()-1]))))bag.pop_back();
		bag.push_back(t);
	}
	return poly(bag).toPoly();
}

poly poly::AconHull()const{
	if(pnt.size()<2)return*this;
	vector<node>nds=(pnt);
	sort(nds.begin(),nds.end(),[](const node&x,const node&y){return x.x<y.x||(zero(x.x-y.x)&&x.y<y.y);});
	deque<node>dnbag,upbag;
	for(auto&t:nds){
		if(!dnbag.empty()&&t==dnbag.back())continue;
		else{
			while(dnbag.size()>1&&(((dnbag[dnbag.size()-1]-dnbag[dnbag.size()-2])^(t-dnbag[dnbag.size()-1]))<0||zero((dnbag[dnbag.size()-1]-dnbag[dnbag.size()-2])^(t-dnbag[dnbag.size()-1]))))dnbag.pop_back();
		}
		dnbag.push_back(t);
	}
	dnbag.pop_back();
	for(auto&t:nds){
		if(!upbag.empty()&&t==upbag.back())continue;
		else{
			while(upbag.size()>1&&(((upbag[upbag.size()-1]-upbag[upbag.size()-2])^(t-upbag[upbag.size()-1]))>0||zero((upbag[upbag.size()-1]-upbag[upbag.size()-2])^(t-upbag[upbag.size()-1]))))upbag.pop_back();
		}
		upbag.push_back(t);
	}
	upbag.pop_front();
	reverse(upbag.begin(),upbag.end());
	vector<node>bag;
	for(auto&t:dnbag){
		bag.push_back(t);
	}
	for(auto&t:upbag){
		bag.push_back(t);
	}
	return poly(bag).toPoly();
}

//lines:
vector<node>lns::ihf(){
	sort(lines.begin(),lines.end());
	deque<line>e(1,lines[0]);
	deque<node>p;
	for(int i=1;i<lines.size();++i)
		if(!(lines[i].dir||e.back().dir)){
		while(p.size()&&p.back()%lines[i]>=0)e.pop_back(),p.pop_back();
		while(p.size()&&p.front()%lines[i]>=0)e.pop_front(),p.pop_front();
		p.push_back(lines[i]*e.back());e.push_back(lines[i]);
	}
	while(p.size()&&p.back()%e.front()>=0)e.pop_back(),p.pop_back();
	p.push_back(e.front()*e.back());
	return vector<node>(p.begin(),p.end());
}//半平面交

template<typename T>
void println(const T&h){
	h.print();
	cout<<endl;
}
vec a[2010];

bool cmp(vec x,vec y){
	return x.agl()<y.agl();
}

int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i+=1){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i+=1){
		a[i+n]=a[i];
	}
	double m=0;
	for(int l=1;l<=n;l+=1){
		vec ans(0,0);
		for(int r=1;r<=n;r+=1){
			ans=ans+a[l+r-1];
			m=max(m,ans.abs());
		}
	}
	cout<<fixed<<setprecision(14)<<m<<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Engines
User WA_King
Language C++14 (GCC 5.4.1)
Score 600
Code Size 10697 Byte
Status AC
Exec Time 3 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 7
AC × 41
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt, 00-sample-05.txt, 00-sample-06.txt, 00-sample-07.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt, 00-sample-05.txt, 00-sample-06.txt, 00-sample-07.txt, 01-random-very-small-01.txt, 01-random-very-small-02.txt, 01-random-very-small-03.txt, 02-random-small-01.txt, 02-random-small-02.txt, 02-random-small-03.txt, 03-random-01.txt, 03-random-02.txt, 03-random-03.txt, 04-zero-01.txt, 05-same-01.txt, 05-same-02.txt, 06-linear-01.txt, 06-linear-02.txt, 06-linear-03.txt, 07-linear-positive-01.txt, 07-linear-positive-02.txt, 07-linear-positive-03.txt, 08-90-degree-01.txt, 08-90-degree-02.txt, 09-180-degree-01.txt, 09-180-degree-02.txt, 10-sandglass-01.txt, 10-sandglass-02.txt, 11-circle-01.txt, 11-circle-02.txt, 11-circle-03.txt, 11-circle-04.txt, 11-circle-05.txt, 12-square-01.txt, 12-square-02.txt, 12-square-03.txt, 13-corner-01.txt, 13-corner-02.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 3 ms 512 KB
00-sample-02.txt AC 1 ms 256 KB
00-sample-03.txt AC 1 ms 256 KB
00-sample-04.txt AC 1 ms 256 KB
00-sample-05.txt AC 1 ms 256 KB
00-sample-06.txt AC 1 ms 256 KB
00-sample-07.txt AC 1 ms 256 KB
01-random-very-small-01.txt AC 1 ms 256 KB
01-random-very-small-02.txt AC 1 ms 256 KB
01-random-very-small-03.txt AC 1 ms 256 KB
02-random-small-01.txt AC 1 ms 256 KB
02-random-small-02.txt AC 2 ms 512 KB
02-random-small-03.txt AC 1 ms 256 KB
03-random-01.txt AC 1 ms 256 KB
03-random-02.txt AC 1 ms 256 KB
03-random-03.txt AC 1 ms 256 KB
04-zero-01.txt AC 1 ms 256 KB
05-same-01.txt AC 1 ms 256 KB
05-same-02.txt AC 1 ms 256 KB
06-linear-01.txt AC 1 ms 256 KB
06-linear-02.txt AC 1 ms 256 KB
06-linear-03.txt AC 1 ms 256 KB
07-linear-positive-01.txt AC 1 ms 256 KB
07-linear-positive-02.txt AC 1 ms 256 KB
07-linear-positive-03.txt AC 1 ms 256 KB
08-90-degree-01.txt AC 1 ms 256 KB
08-90-degree-02.txt AC 1 ms 256 KB
09-180-degree-01.txt AC 1 ms 256 KB
09-180-degree-02.txt AC 1 ms 256 KB
10-sandglass-01.txt AC 1 ms 256 KB
10-sandglass-02.txt AC 1 ms 256 KB
11-circle-01.txt AC 1 ms 256 KB
11-circle-02.txt AC 1 ms 256 KB
11-circle-03.txt AC 1 ms 256 KB
11-circle-04.txt AC 1 ms 256 KB
11-circle-05.txt AC 1 ms 256 KB
12-square-01.txt AC 1 ms 256 KB
12-square-02.txt AC 1 ms 256 KB
12-square-03.txt AC 1 ms 256 KB
13-corner-01.txt AC 1 ms 256 KB
13-corner-02.txt AC 1 ms 256 KB