QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648758 | #7800. Every Queen | qinglu09 | TL | 602ms | 6196kb | C++14 | 8.1kb | 2024-10-17 20:13:04 | 2024-10-17 20:13:25 |
Judging History
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)
{
for(auto v:nwl)
{
if(relation_l_l(p,v)==1)
{
nwll.push_back(p);
}
else 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: 0ms
memory: 3800kb
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: 0ms
memory: 3800kb
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: 3776kb
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: 45ms
memory: 3900kb
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: 3924kb
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: 108ms
memory: 3780kb
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: 22ms
memory: 3912kb
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: 27ms
memory: 3780kb
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: 3908kb
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: 49ms
memory: 3912kb
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: 3988kb
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: 51ms
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: 36ms
memory: 3988kb
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: 22ms
memory: 6196kb
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: 3828kb
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: 1ms
memory: 4004kb
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: 59ms
memory: 3912kb
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: 52ms
memory: 3920kb
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: 75ms
memory: 3804kb
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: 62ms
memory: 3908kb
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: 56ms
memory: 3996kb
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: 90ms
memory: 3976kb
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: 306ms
memory: 4044kb
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: 602ms
memory: 4160kb
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...