QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648775#7800. Every Queenqinglu09TL 616ms6184kbC++148.3kb2024-10-17 20:21:372024-10-17 20:21:38

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 20:21:38]
  • 评测
  • 测评结果:TL
  • 用时:616ms
  • 内存:6184kb
  • [2024-10-17 20:21:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
#define lowbit(x) (x&-x)
#define gcd __gcd
#define i128 __int128
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const int N=1e6+10,M=1e3+10;
const ll mod=1e9+7;
const ld eps=1e-12;
const double pi=acos(-1.0);
const double pi1=pi/180,pi2=180/pi;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//unordered_map<int,int>mp;
#define poly vector<int>

#define double ld

double dtopi(double x) {return x*pi1;}
double pitod(double x) {return x*pi2;}
int sgn(double x) 
{
    if(fabs(x)<eps) return 0;	// x == 0, 精度范围内的近似相等
    return x>0?1:-1;			// 返回正负
}

typedef struct point 
{
    double x,y;
    point(double x = 0, double y = 0) : x(x), y(y) {}
    double operator * (point b) {return x*b.x+y*b.y;}//点乘
	double operator ^ (point b) {return x*b.y-y*b.x;}//叉乘
	point operator + (point b) {return point(x+b.x,y+b.y);}
	point operator - (point b) {return point(x-b.x,y-b.y);}
	bool operator == (const point &b) const {return sgn(x-b.x)==0&&sgn(y-b.y)==0;}
	bool operator < (const point &b) const {return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;}
	bool operator > (point b) {return !(*this<b);}
	point operator * (double k) {return point(k*x,k*y);}//数乘
	point operator / (double k) {return point(x/k,y/k);}//数除
    double len() {return hypot(x,y);}//模长
	double len2() {return x*x+y*y;}//模长平方
	point trunc(double r) {double l=len();r/=l;return point(x*r,y*r);}//变模长为r
	double dis(point b){return hypotl(x-b.x,y-b.y);}
	double angle() {return atan2(y,x);}
	int quad() {return sgn(y)>0||sgn(y)==0&&sgn(x)>0;}//0:[-π,0)  1:[0,π)
	point unit() {return *this/len();}//单位向量
}Vector;
double len(Vector a) {return sqrtl(a*a);}//模长
double dis(point a,point b) {return (a-b).len();}
double dis2(point a,point b) {return (a-b).len2();}
double norm(double x)//返回弧度[0,2π)
{
    while(x<0) x+=2*pi;
    while(x>=2*pi) x-=2*pi;
    return x;
}

double angle(Vector a,Vector b)//a到b的夹角
{
    double t=acos((a*b)/len(a)/len(b));
    return t;           // 返回 [0,π]
    //return pitod(t);  // 返回 [0,180]
}

double rad(Vector a,Vector b)//角aob弧度大小
{
	return fabs(atan2(fabs(a^b),a*b));
}

point rotleft(point a) {return point(-a.y,a.x);}//逆时针旋转90度
point rotright(point a) {return point(a.y,-a.x);}//顺时针旋转90度
point rotate(point a,point o,double angle)//点a绕点p逆时针旋转弧度angle [0,π]
{
	point v=a-o;
	double c=cos(angle),s=sin(angle);
	return point(o.x+v.x*c-v.y*s,o.y+v.x*s+v.y*c);
}
Vector Rotate(Vector a,double angle)//向量旋转弧度angle [0,π]
{
    Vector b(sin(angle),cos(angle));
    return Vector(a^b,a*b);
}

//1:  b在a的逆时针方向
//-1: b在a的顺时针方向
//2:  b与a同向共线
//-2: b在a反向共线
int cross(Vector a,Vector b)//向量b与a的方位关系
{
	int x=sgn(a^b),y=sgn(a*b);
	if(x!=0) return x;
	else return 2*y;
}
bool sameline(point a,point b,point c) {return sgn((b-a)^(c-b))==0;}//三点共线
double cross(point a,point b,point c) {return (b-a)^(c-a);}//ab叉乘ac
double dot(point a,point b,point c) {return (b-a)*(c-a);}//ab点乘ac

typedef struct line
{
	point s,e;
	line(){}
	line(point _s,point _e) {s =_s; e= _e;}
	line(point p,double angle)//点斜
	{
		s=p;
		if(sgn(angle-pi/2)==0)  e=(s+point(0,1));
		else e=(s+point(1,tan(angle)));
	}
	line(double a,double b,double c)//ax+by+c=0;
	{
		if(sgn(a)==0) {s=point(0,-c/b);e=point(1,-c/b);}
		else if(sgn(b)==0) {s=point(-c/a,0);e=point(-c/a,1);}
		else {s=point(0,-c/b);e=point(1,(-c-a)/b);}
	}
	double length() {return s.dis(e);}//线段长度
	double angle1()//返回[0,π]的基于x轴的斜倾角(弧度制)
	{
		double k=atan2(e.y-s.y,e.x-s.x);
		if(sgn(k)<0) k+=pi;
		if(sgn(k-pi)==0) k-=pi;
		return k;
	}
	double angle2()//返回(-π,π]的基于x正半轴的斜倾角(弧度制)
	{
		return atan2(e.y-s.y,e.x-s.x);
	}
}seg;

//-1: 在右侧(顺时针)
//1:  在左侧(逆时针)
//0:  在直线上
int relation_p_l(point p,line l) {return sgn((p-l.s)^(l.e-l.s));}//点与直线关系

double dis_p_l(point p,line l) {return fabs((p-l.s)^(l.e-l.s))/l.length();}//点到直线的距离

point prog(point p,line l)//点p在直线l上的投影点(垂足)
{
	point x=l.e-l.s;
	return l.s+((x*(x*(p-l.s)))/(x.len2()));
}

point mirror(point p,line l)//点p在直线l上的对称点
{
	point q=prog(p,l);
	return point(2*q.x-p.x,2*q.y-p.y);
}

bool relation_p_seg(point p,seg l)//点是否在线段上
{
	return sgn((p-l.s)^(l.e-l.s))==0&&sgn((p-l.s)*(p-l.e))<=0;
}

double dis_p_seg(point p,seg l)//点到线段的距离
{
	if(sgn((p-l.s)*(l.e-l.s))<0||sgn((p-l.e)*(l.s-l.e))<0)
		return min(p.dis(l.s),p.dis(l.e));
	return dis_p_l(p,l);
}

bool parallel(line l,line v) {return sgn((l.e-l.s)^(v.e-v.s))==0;}//判断平行

//0:  平行
//1:  共线
//-1: 相交
int relation_l_l(line l,line v)//判断两直线的位置关系
{
	if(parallel(l,v)) return relation_p_l(l.s,v)==0;
	return -1;
}

//-1: 规范相交
//1:  非规范相交(顶点处相交)
//0:  不相交
int relation_l_seg(line l,seg v)//直线与线段位置关系
{
	int d1=sgn((l.e-l.s)^(v.s-l.s));
	int d2=sgn((l.e-l.s)^(v.e-l.s));
	if((d1^d2)==-2) return -1;
	return (d1==0||d2==0);
}

//-1: 规范相交(恰有一个交点且非端点,即互相穿过)
//1:  非规范相交
//0:  不相交
int is_segcrossseg(seg l,seg v)//两线段相交判断
{
	int d1=sgn((l.e-l.s)^(v.s-l.s));
	int d2=sgn((l.e-l.s)^(v.e-l.s));
	int d3=sgn((v.e-v.s)^(l.s-v.s));
	int d4=sgn((v.e-v.s)^(l.e-v.s));
	if ((d1^d2)==-2&&(d3^d4)==-2) return -1;
	
	return (d1==0&&sgn((v.s-l.s)*(v.s-l.e))<=0)||
	(d2==0&&sgn((v.e-l.s)*(v.e-l.e))<=0)||
	(d3==0&&sgn((l.s-v.s)*(l.s-v.e))<=0)||
	(d4==0&&sgn((l.e-v.s)*(l.e-v.e))<=0);
}

double dis_seg_seg(seg l,seg v)//线段到线段的距离
{
	if(is_segcrossseg(l,v)) return 0; 
	return min(min(dis_p_seg(v.s,l),dis_p_seg(v.e,l)),min(dis_p_seg(l.s,v),dis_p_seg(l.e,v)));
}

point lcrossl(line a,line b)//求两直线的交点(需要保证直线不平行或共线)
{	
	point u=a.s-b.s,v=a.e-a.s,w=b.e-b.s;

	//***************************
	if((w^v)==0)//o2优化出问题的时候直接返回mle,
	{
		vector<int>q;
		while(1) q.push_back(1);
	}
	//***************************

  	double t=(u^w)/(w^v);
  	return a.s+v*t;
}

point add[4];
int num=0;
void solve()
{
	num++;
    int n;
	cin>>n;
	point a[n+1];
	for(int i=1;i<=n;i++)
	{
		ll x,y;
		cin>>x>>y;
		a[i]={x,y};
	}
	vector<line>stl;
	vector<point>stp;
	for(int i=0;i<4;i++) stl.push_back(line(a[1],a[1]+add[i]));
	for(int i=2;i<=n;i++)
	{
		vector<point>nwp;
		vector<line>nwl,nwll;
		for(int j=0;j<4;j++) nwl.push_back(line(a[i],a[i]+add[j]));
		for(auto p:stp)
		{
			int fact=0;
			for(auto v:nwl)
			{
				if(relation_p_l(p,v)==0) fact=1;
			}
			if(fact) nwp.push_back(p);
		}
		for(auto p:stl)
		{
			int fact=0;
			for(auto v:nwl)
			{
				if(relation_l_l(p,v)==1)
				{
					nwll.push_back(p);
					fact=1;
				}
				else if(relation_l_l(p,v)==-1)
				{
					nwp.push_back(lcrossl(p,v));
				}
			}
			if(!fact)
			{
				for(auto v:nwl)
				{
					if(relation_l_l(p,v)==-1)
					{
						nwp.push_back(lcrossl(p,v));
					}
				}
			}
		}
		stp=nwp;
		stl=nwll;
	}
	for(auto p:stp)
	{
		//if(num==317&&round(stp[0].x)==2) cout<<fixed<<setprecision(13)<<stp[0].x<<" "<<stp[0].y<<endl;
		if(sgn(round(p.x)-p.x)==0)
		{
			cout<<"YES"<<endl;
			cout<<fixed<<setprecision(0)<<p.x<<" "<<p.y<<endl;
			return;
		}
	}
	if(stl.size())
	{
		cout<<"YES"<<endl;
		//if(num==317&&round(stl[0].s.x)==2) cout<<"123456 123456"<<endl;
		cout<<fixed<<setprecision(0)<<stl[0].s.x<<" "<<stl[0].s.y<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	//for(auto [x,y]:stp) cout<<x<<" "<<y<<" ";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T=1;
	cin>>T;

	add[0]={1,0};
	add[1]={0,1};
	add[2]={1,1};
	add[3]={1,-1};

	while(T--)
	{
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3968kb

input:

3
2
1 1
2 2
4
0 1
1 0
3 1
4 0
5
0 1
1 0
1 2
2 2
4 2

output:

YES
2 1
NO
YES
1 2

result:

ok OK (3 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

1
4
-100000000 -100000000
100000000 -100000000
-100000000 100000000
100000000 100000000

output:

YES
100000000 -100000000

result:

ok OK (1 test case)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

330
3
5 1
-3 -5
-2 2
2
1 4
4 0
4
2 -5
3 -3
-5 4
2 -2
2
-4 1
2 4
1
1 5
4
3 5
-2 3
5 2
-3 -3
5
-3 -4
2 -1
-2 -2
1 0
-1 -5
5
4 -3
-2 -4
2 2
0 -5
-4 -3
4
0 0
-3 -5
0 5
5 0
1
1 -1
5
0 2
3 4
1 4
4 5
5 0
3
-4 -5
-5 -3
5 -5
3
-1 2
-4 -4
-1 5
4
1 1
4 5
-1 0
5 2
1
-3 2
5
5 0
4 1
-3 -5
3 -3
0 0
5
0 1
-5 4
-5 5...

output:

YES
-3 1
YES
4 4
YES
2 -3
YES
2 1
YES
1 5
NO
NO
NO
YES
0 -5
YES
1 -1
NO
YES
-5 -5
YES
-4 2
YES
1 2
YES
-3 2
NO
YES
-5 -4
YES
2 0
YES
-5 -3
YES
-2 0
NO
YES
2 0
YES
0 -1
YES
5 1
YES
0 -1
YES
1 5
YES
-5 -2
YES
4 6
NO
YES
5 -4
NO
YES
1 -4
YES
3 5
YES
-1 3
YES
-5 1
NO
NO
YES
2 5
YES
2 4
YES
1 -4
YES
-2 -...

result:

ok OK (330 test cases)

Test #4:

score: 0
Accepted
time: 67ms
memory: 3920kb

input:

33773
4
-2 -5
4 -1
-5 4
2 -1
3
5 1
1 0
-2 4
1
-5 -4
4
-3 1
5 -1
1 -2
-3 5
2
-2 -2
0 2
4
-2 -1
4 -5
1 1
1 -4
3
-5 -5
-5 0
-3 -5
1
-3 0
4
-5 -4
2 2
-5 -3
5 -3
1
-5 0
2
-3 -3
-4 -3
1
3 -2
3
-2 -2
5 -4
5 -3
2
5 -1
-5 2
4
0 -1
5 1
0 0
-4 -1
1
-5 4
4
-5 3
3 0
-1 -3
0 3
2
4 0
0 -3
2
-2 4
0 1
2
-3 3
4 1
3
-...

output:

NO
YES
1 1
YES
-5 -4
NO
YES
0 -2
NO
YES
-5 -5
YES
-3 0
NO
YES
-5 0
YES
-4 -3
YES
3 -2
YES
5 -2
YES
-5 -1
NO
YES
-5 4
NO
YES
0 0
YES
0 4
YES
4 3
YES
-2 -3
NO
YES
0 1
YES
3 5
NO
NO
YES
0 0
YES
-4 -4
YES
2 -3
YES
4 -5
YES
0 3
YES
4 4
NO
YES
-3 3
NO
YES
1 -3
YES
-3 5
NO
NO
YES
2 1
NO
YES
-3 1
YES
1 -1
N...

result:

ok OK (33773 test cases)

Test #5:

score: 0
Accepted
time: 64ms
memory: 3984kb

input:

100000
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0
1
0 0...

output:

YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
0 0
YES
...

result:

ok OK (100000 test cases)

Test #6:

score: 0
Accepted
time: 79ms
memory: 3984kb

input:

41344
4
-2 1
-1 -1
2 -1
-1 2
2
1 2
-1 1
2
-1 2
1 -2
3
-1 2
1 -2
-2 0
3
2 -1
1 2
1 -2
2
0 -1
-1 0
1
-1 2
1
-2 -1
1
2 2
3
0 -2
-2 -2
0 1
4
2 -1
-2 2
-1 0
-2 1
3
0 0
1 1
2 2
3
0 -1
-1 -1
-2 -1
1
-2 -1
1
0 -1
1
0 0
1
-2 -2
2
1 -1
-2 -1
4
-2 -1
1 1
0 -1
-2 0
4
-1 1
-2 0
2 2
0 2
2
1 -2
-1 1
4
2 1
-2 1
-1 ...

output:

YES
-4 -1
YES
-1 2
YES
1 2
YES
-1 0
YES
1 -1
YES
-1 -1
YES
-1 2
YES
-2 -1
YES
2 2
YES
0 -2
YES
-2 -1
YES
0 0
YES
-1 -1
YES
-2 -1
YES
0 -1
YES
0 0
YES
-2 -2
YES
-2 -1
YES
-1 -1
YES
0 0
YES
-1 -2
YES
2 5
YES
1 2
YES
1 2
YES
0 0
YES
-1 -1
YES
1 2
YES
1 0
YES
-2 2
YES
2 0
YES
-1 2
YES
0 0
YES
2 0
YES
0 ...

result:

ok OK (41344 test cases)

Test #7:

score: 0
Accepted
time: 37ms
memory: 3812kb

input:

10663
7
3 1
-1 -1
1 2
0 1
3 0
2 -2
-2 -1
11
2 -2
1 -2
-1 0
1 3
-3 0
2 2
-1 -3
1 2
3 -1
-3 3
2 0
8
-2 0
0 -2
1 1
-2 -1
-3 -3
-2 -3
-1 0
1 0
15
2 -3
-3 2
1 1
-2 1
-2 -2
3 3
-2 0
-1 -1
-1 2
0 3
0 1
-3 1
0 0
0 2
-2 -3
10
-1 0
0 2
-3 -2
-1 -1
0 0
-3 0
1 2
0 -1
-3 -3
2 2
4
-1 0
3 -2
-3 0
3 2
8
-3 0
2 -1
-...

output:

NO
NO
NO
NO
NO
YES
3 0
NO
YES
1 -3
NO
NO
YES
-2 0
YES
-3 -2
NO
NO
NO
NO
NO
NO
NO
NO
YES
3 -1
NO
YES
3 -2
NO
NO
YES
2 -2
YES
-3 2
NO
NO
YES
3 2
NO
YES
3 1
NO
YES
1 -1
NO
NO
YES
0 2
NO
NO
NO
NO
NO
YES
2 1
NO
NO
YES
5 3
NO
NO
NO
YES
-3 2
NO
NO
NO
NO
NO
NO
NO
YES
-3 -2
NO
NO
NO
NO
NO
NO
NO
YES
0 1
YES
0...

result:

ok OK (10663 test cases)

Test #8:

score: 0
Accepted
time: 32ms
memory: 3920kb

input:

9675
4
5 -8
-6 -10
10 2
-1 10
8
-8 -1
-9 4
-10 -2
-8 -8
-10 1
-8 -5
2 -4
-3 4
2
2 -5
-3 -4
18
6 -2
8 -7
3 -2
10 8
-2 -2
-1 -10
0 -6
-6 10
9 0
7 -1
-4 10
2 3
-9 -3
5 -9
0 -1
8 5
-9 -7
0 6
14
5 -8
4 9
-2 7
-6 -4
-8 -5
3 -10
2 1
-6 1
-8 -6
-5 -10
-10 0
-7 9
9 7
10 -10
3
2 3
2 4
-8 2
2
0 10
5 1
8
-5 -5
...

output:

NO
NO
YES
-3 -5
NO
NO
YES
2 2
YES
5 10
NO
NO
NO
NO
NO
YES
-5 -1
NO
YES
-5 -9
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
4 0
NO
NO
NO
NO
NO
NO
NO
YES
-2 -7
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
-7 -6
NO
NO
NO
NO
NO
NO
NO
NO
YES
1 -10
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
1 -9
YES
5...

result:

ok OK (9675 test cases)

Test #9:

score: 0
Accepted
time: 36ms
memory: 3984kb

input:

18336
2
-28 -3
-27 -8
2
21 -25
23 18
6
2 -16
-24 0
19 -18
-7 8
12 -29
29 20
7
-22 -16
8 -28
12 -9
5 14
18 -15
16 -7
26 -12
3
-21 -30
26 18
15 13
5
29 12
-30 -27
-15 -15
7 -3
-6 -20
8
-28 -11
27 8
25 8
11 14
3 -15
3 -14
1 -14
28 -25
8
-11 -9
-7 14
-30 1
19 -29
21 -25
-14 -14
-25 -15
3 17
5
13 4
-23 -...

output:

YES
-27 -3
YES
23 -25
NO
NO
NO
NO
NO
NO
NO
YES
23 -4
NO
YES
21 16
NO
YES
16 -11
NO
NO
NO
NO
NO
YES
0 21
YES
-9 29
NO
NO
NO
NO
YES
6 -12
NO
NO
NO
NO
YES
29 5
NO
NO
NO
YES
-14 16
NO
NO
YES
-23 -24
YES
12 9
NO
NO
NO
NO
YES
20 -24
YES
28 -30
YES
21 24
YES
-10 -2
YES
16 -18
NO
NO
NO
YES
-12 -1
NO
NO
NO
N...

result:

ok OK (18336 test cases)

Test #10:

score: 0
Accepted
time: 68ms
memory: 3904kb

input:

39738
2
31 35
44 8
1
4 -28
2
12 43
-12 13
2
-16 -16
19 -6
3
-1 40
-18 11
17 -46
1
9 36
4
29 -32
13 -7
5 24
18 -31
3
-13 -43
-2 -50
-10 31
2
-25 -12
-20 30
1
49 29
2
14 41
49 19
4
45 -26
5 26
15 21
-9 0
4
-29 6
0 41
34 -11
-7 -3
1
-35 18
4
-31 50
-33 16
-36 -19
9 12
4
-11 -8
2 37
6 13
5 -40
1
30 20
2...

output:

YES
44 35
YES
4 -28
YES
-12 43
YES
19 -16
NO
YES
9 36
NO
NO
YES
-20 -12
YES
49 29
YES
49 41
NO
NO
YES
-35 18
NO
NO
YES
30 20
YES
-44 -3
YES
-36 8
YES
-5 21
YES
-24 34
NO
YES
-7 15
YES
45 2
YES
-23 31
YES
-15 -32
NO
YES
31 46
YES
34 -41
NO
YES
43 32
YES
-36 -28
NO
YES
16 25
YES
-46 16
NO
NO
YES
-28 -...

result:

ok OK (39738 test cases)

Test #11:

score: 0
Accepted
time: 97ms
memory: 3972kb

input:

100000
1
25720 -7437
1
41161 -43283
1
301 -2068
1
-83347 60319
1
-81716 28835
1
-72575 65116
1
8859 -27828
1
34738 92440
1
80487 91784
1
-5793 -21239
1
-60334 -75846
1
79009 -16026
1
78558 -1651
1
-52829 -58727
1
-2153 -58876
1
-64746 30799
1
69134 82923
1
-10500 -77083
1
-15959 -46509
1
17184 18402...

output:

YES
25720 -7437
YES
41161 -43283
YES
301 -2068
YES
-83347 60319
YES
-81716 28835
YES
-72575 65116
YES
8859 -27828
YES
34738 92440
YES
80487 91784
YES
-5793 -21239
YES
-60334 -75846
YES
79009 -16026
YES
78558 -1651
YES
-52829 -58727
YES
-2153 -58876
YES
-64746 30799
YES
69134 82923
YES
-10500 -77083
...

result:

ok OK (100000 test cases)

Test #12:

score: 0
Accepted
time: 63ms
memory: 3988kb

input:

33248
4
4011 53911
-65222 72560
-58309 -72652
54087 -77099
3
84215 93494
-39147 9885
-99743 50164
4
-86020 42500
-31132 51501
-95265 -73272
79336 -52301
3
35424 75664
68639 -55324
-97553 -81811
5
-52662 -87598
-61048 -71133
57071 -96841
-92280 96599
-12314 79758
5
-30239 91586
-42080 -30101
47354 11...

output:

NO
NO
NO
NO
NO
NO
NO
YES
2728 -18491
YES
-47798 15233
NO
NO
NO
YES
56239 -88858
YES
-70441 94465
NO
NO
NO
NO
NO
YES
-11524 -44157
YES
51015 -56275
YES
18706 -99023
NO
YES
33027 69204
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
19340 -59579
NO
YES
-70292 -30378
NO
YES
76496 -29089
YES
-97591 16425
YES
41714 87917...

result:

ok OK (33248 test cases)

Test #13:

score: 0
Accepted
time: 45ms
memory: 3860kb

input:

18213
2
83560 -16394
-64607 -2972
4
-97408 -96045
73180 -49275
77310 -53026
60293 82128
2
89814 -68477
9551 2526
4
45152 53548
-98942 91447
76012 71607
-54940 53136
1
53895 13657
2
6991 5450
-48933 8147
2
2375 89999
-23250 71842
9
52896 -51251
-41169 -74405
-9804 -58661
99052 -65848
93012 16117
5504...

output:

YES
-64607 -16394
NO
YES
9551 -68477
NO
YES
53895 13657
YES
-48933 5450
YES
-23250 89999
NO
NO
YES
13717 -44761
NO
NO
YES
-56119 -27970
NO
NO
YES
-59545 42679
NO
YES
84770 -65606
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
70930 -16981
NO
NO
NO
NO
YES
91247 59737
YES
1714 -52312
NO
YES
-52273 -73438
NO
YES...

result:

ok OK (18213 test cases)

Test #14:

score: 0
Accepted
time: 23ms
memory: 6184kb

input:

12
73282
48456 9658
-44253 -47777
70415 89736
-7902 -40555
21517 -46397
12398 64467
-76104 -83148
-36156 91008
-71906 -12870
-56634 9176
-29904 83593
43413 -21468
23018 38228
-39705 -9294
78799 80256
51880 -32455
-27784 94899
-48629 -22413
-57032 -60008
-96094 45483
90292 88165
-59153 -78792
55143 -...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
22817 54633

result:

ok OK (12 test cases)

Test #15:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

376
3
21 -12
-44 56
-29 71
1
-37 -6
5
-51 49
3 25
-7 69
-19 47
-32 60
3
-89 19
6 -75
-33 75
4
-82 4
-66 -29
-55 4
-51 4
1
-98 -59
3
-53 -53
-10 25
-28 -51
1
-54 55
3
50 -55
-44 -19
-6 -33
3
44 -10
2 20
16 -41
3
90 99
81 55
81 83
3
-47 18
-4 59
-12 53
1
43 98
1
-57 12
1
-5 -1
4
48 89
-41 -45
-75 -79
...

output:

YES
-112 -12
YES
-37 -6
NO
YES
-183 -75
YES
-66 4
YES
-98 -59
NO
YES
-54 55
NO
NO
YES
81 99
YES
-6 59
YES
43 98
YES
-57 12
YES
-5 -1
YES
93 89
YES
23 1
YES
47 -52
YES
-60 16
YES
52 -71
NO
YES
-121 34
YES
-16 -91
YES
59 74
YES
-20 -29
YES
50 36
YES
-65 -77
YES
-39 -94
YES
62 -10
YES
-46 -98
YES
-10 -...

result:

ok OK (376 test cases)

Test #16:

score: 0
Accepted
time: 2ms
memory: 3892kb

input:

36
7
5 -12
-37 -46
-62 -12
-19 -30
-60 -12
-48 -12
-65 -12
53
75 16
38 16
49 16
88 16
27 16
36 16
55 16
53 16
95 16
94 16
20 16
21 -21
65 16
70 16
69 16
66 16
76 16
33 16
58 -33
44 16
59 16
72 16
8 16
23 16
9 16
13 16
64 16
32 16
58 0
24 16
48 16
100 16
41 16
67 16
68 16
22 16
87 16
73 16
39 16
12 1...

output:

YES
-37 -12
YES
58 16
YES
26 100
YES
-74 -14
NO
YES
77 4
YES
58 -20
NO
YES
-21 7
YES
-38 4
YES
56 -100
YES
-88 -50
YES
37 -96
YES
97 -27
YES
-60 -93
NO
YES
15 80
YES
83 72
YES
-56 87
YES
57 -20
YES
-111 87
YES
-38 -46
YES
23 -47
NO
NO
YES
-98 -12
YES
10 17
YES
-81 -13
YES
9 -24
YES
-37 -97
YES
-28 -...

result:

ok OK (36 test cases)

Test #17:

score: 0
Accepted
time: 76ms
memory: 3788kb

input:

38250
1
-71 -9
5
-35 4
13 17
36 4
-4 4
-11 4
2
32 -58
-6 -73
3
-66 -21
-65 -20
-66 -62
1
-47 -90
1
67 -1
1
-40 -34
3
-12 71
-46 71
-68 71
3
-45 85
-6 60
-9 82
2
8 84
86 -47
3
-63 55
30 90
-56 40
5
81 -27
-74 -20
-30 53
-69 -15
-30 -2
5
-69 -51
-38 -56
3 -97
-43 -96
-70 -24
1
-85 -75
5
-15 -53
-95 -1...

output:

YES
-71 -9
YES
13 4
YES
-6 -58
YES
-66 -21
YES
-47 -90
YES
67 -1
YES
-40 -34
YES
-46 71
YES
-6 85
YES
86 84
NO
NO
YES
-43 -51
YES
-85 -75
NO
YES
61 69
YES
-61 -29
YES
-31 59
YES
-97 39
YES
26 89
YES
-61 -47
YES
14 41
YES
-18 55
YES
33 -18
YES
37 47
YES
13 0
YES
-28 -84
YES
-20 -59
YES
-48 8
YES
-51 ...

result:

ok OK (38250 test cases)

Test #18:

score: 0
Accepted
time: 63ms
memory: 3980kb

input:

21678
7
57 83
63 77
68 72
45 95
85 55
71 69
60 96
4
51 91
44 84
43 -55
53 51
2
-86 81
5 -56
3
-48 -6
-80 -38
-62 6
7
-15 73
-15 59
-15 83
-15 49
-15 76
-15 94
-15 60
9
-13 8
-13 17
-13 18
-13 -50
-13 35
-13 -23
-13 34
-13 -6
-13 42
3
40 -63
83 -36
44 -67
5
-57 64
-47 40
-54 40
-95 40
-22 40
9
-87 -7...

output:

YES
44 96
NO
YES
5 81
YES
-36 6
YES
-15 73
YES
-13 8
YES
13 -36
YES
-57 40
NO
NO
YES
91 -62
NO
YES
98 50
YES
93 -56
NO
YES
34 -84
YES
-12 14
NO
YES
-2 -84
YES
73 77
NO
NO
YES
-43 10
YES
-94 30
YES
-32 -29
YES
-18 -49
NO
NO
YES
60 -56
YES
95 -78
YES
-142 -64
YES
-24 91
YES
-76 -94
YES
77 5
YES
-94 -9...

result:

ok OK (21678 test cases)

Test #19:

score: 0
Accepted
time: 89ms
memory: 3988kb

input:

38031
2
34020723 8239345
96663022 -53883165
3
86840549 -42430280
71644095 5956538
49933723 30642832
5
55112712 33477733
33812854 13213047
55468132 -8442231
63342437 -16316536
45778536 33477733
5
-40033178 50867370
-8653896 53384752
-9420867 50867370
-3826315 50867370
12182283 50867370
3
-69673375 91...

output:

YES
96663022 8239345
NO
YES
13548168 33477733
YES
-8653896 50867370
NO
YES
41805462 -32093861
NO
YES
-95477857 6807868
YES
36874106 -60563234
YES
29067626 -37879764
YES
-56081973 -20683199
YES
44076829 49930482
YES
-44728643 77741768
YES
15739506 -7131626
YES
79270965 32547632
YES
17818216 -95715243...

result:

ok OK (38031 test cases)

Test #20:

score: 0
Accepted
time: 68ms
memory: 3988kb

input:

21402
2
-64579901 -74329677
-20994959 -45151167
4
76282770 54962460
76282770 90135060
76282770 87339000
76282770 90059212
7
-78215169 9670558
-29772494 9670558
-58300956 9670558
-20921867 9670558
-5374544 9670558
-60834676 9670558
-77752192 9670558
2
72103587 61733561
41131637 93025543
2
48107017 -9...

output:

YES
-20994959 -74329677
YES
76282770 54962460
YES
-29772494 9670558
YES
41131637 61733561
YES
57003686 -98610264
NO
YES
95305394 -65871859
YES
43703288 47064195
YES
55394883 99392942
YES
16429362 22770100
YES
136838075 -15006182
NO
YES
9823557 99931203
YES
-15252818 47155441
YES
61765950 -87825931
Y...

result:

ok OK (21402 test cases)

Test #21:

score: 0
Accepted
time: 65ms
memory: 3992kb

input:

11466
15
59883513 -2073195
72007848 10051140
72894155 10937447
21210749 -40745959
69730665 7773957
13463482 -48493226
81294534 19337826
82764975 20808267
74693443 12736735
48056353 -13900355
74056094 63649616
26024854 -35931854
30806547 -31150161
51863468 -10093240
26040272 -35916436
1
8906295 76373...

output:

YES
125606324 63649616
YES
8906295 76373253
YES
-66554988 -62523894
YES
41111496 61138114
YES
95075800 52750455
YES
-79116470 54206114
NO
YES
-82740989 -87561097
YES
-22668385 44659674
YES
43299608 18117481
YES
-26462700 63271615
YES
26621720 -72738245
YES
-14780418 -89727803
NO
YES
69343557 6619924...

result:

ok OK (11466 test cases)

Test #22:

score: 0
Accepted
time: 88ms
memory: 3980kb

input:

2374
8
80171282 -7970988
90530464 -7970988
94515630 -7970988
67903596 -7970988
68473134 -7970988
66846181 -7970988
89920403 -7970988
77340189 -7970988
47
-80585182 73218352
-50635638 43268808
-58967884 51601054
-71338457 63971627
-95428893 88062063
-27599821 20232991
-45242309 37875479
-81024686 736...

output:

YES
90530464 -7970988
YES
-80585182 73218352
NO
YES
12164652 40063983
YES
76981122 6496589
YES
13601122 -24205245
YES
-104015503 -19395854
YES
8099865 -65610049
NO
YES
-67654562 52808377
NO
NO
YES
48169366 -19788636
NO
YES
-36480703 -45718682
YES
-22857945 -13904913
YES
13160351 29667948
YES
8352983...

result:

ok OK (2374 test cases)

Test #23:

score: 0
Accepted
time: 313ms
memory: 4132kb

input:

495
64
-21368080 -72850405
-85833696 90257396
-35915936 -58302549
-15925459 -78293026
-30025678 -64192807
-20646405 -73572080
160784 -79015396
-29013484 -65205001
-33711159 -60507326
-56255295 -37963190
-59625837 -34592648
-43071457 -51147028
-56204310 -38014175
-5994443 -88224042
-41934232 -5228425...

output:

NO
YES
-29395158 34645498
YES
-36890600 15479221
NO
NO
YES
-60911690 55429433
YES
59451597 -10114835
NO
YES
4859968 39029958
NO
NO
NO
YES
35039029 72031692
NO
NO
YES
72026368 -25580315
YES
24017187 -9384822
YES
-75397783 -37470215
NO
YES
-47008899 67349531
NO
YES
42236203 69440652
YES
91434570 -9490...

result:

ok OK (495 test cases)

Test #24:

score: 0
Accepted
time: 616ms
memory: 4240kb

input:

248
625
-81955368 42113025
-59734335 19891992
-49896979 10054636
-93943839 54101496
-57293721 17451378
-95370351 55528008
-80969337 41126994
-59859616 20017273
-80746055 40903712
-63054108 23211765
-85729412 45887069
-79459890 39617547
-75207406 35365063
-96821217 56978874
-68473967 28631624
-917114...

output:

YES
-81955368 42113025
NO
NO
YES
-63305508 96308920
YES
146411158 -69515911
YES
-28759823 35797945
YES
-40767426 15678156
NO
YES
60065553 74277233
NO
YES
-95522379 -85240181
YES
69590952 -65105937
YES
42972981 -38779275
YES
-26191094 -21885510
YES
-45739762 88827246
YES
-80160899 -11658069
NO
YES
-1...

result:

ok OK (248 test cases)

Test #25:

score: -100
Time Limit Exceeded

input:

33
6818
-64604806 -76001331
-2467317 -76001331
-57044757 -76001331
-9135480 -76001331
-9998308 -76001331
-72127204 -76001331
-85067127 -76001331
-77665130 -76001331
-33241448 -76001331
-35999647 -76001331
-14392790 -76001331
-67179688 -76001331
-79626590 -76001331
-54021051 -76001331
-51851904 -7600...

output:


result: