CSES - Datatähti Open 2019 - Results
Submission details
Task:Function
Sender:zscoder
Submission time:2019-01-18 11:15:31 +0200
Language:C++
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED45
#20
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.03 s1details
#4ACCEPTED0.02 s1details
#5ACCEPTED0.11 s1details
#6ACCEPTED0.03 s1details
#7ACCEPTED0.03 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.03 s1details
#100.03 s2details
#11ACCEPTED0.02 s2details
#12ACCEPTED0.03 s2details
#13ACCEPTED0.02 s2details
#14ACCEPTED0.13 s2details
#15ACCEPTED0.13 s2details
#16ACCEPTED0.12 s2details
#17ACCEPTED0.12 s2details
#18ACCEPTED0.09 s2details
#19ACCEPTED0.10 s2details
#20ACCEPTED0.08 s2details
#210.01 s2details
#22ACCEPTED0.84 s2details
#23--2details
#24--2details
#25ACCEPTED0.94 s2details
#26ACCEPTED0.94 s2details
#27--2details
#28ACCEPTED0.61 s2details
#29ACCEPTED0.82 s2details
#30ACCEPTED0.02 s2details
#31ACCEPTED0.01 s2details
#32ACCEPTED0.02 s2details
#33ACCEPTED0.02 s2details
#34ACCEPTED0.12 s2details
#35--2details

Compiler report

input/code.cpp: In function 'std::vector<std::pair<long double, long double> > intersect(std::vector<std::pair<long double, long double> >, std::vector<std::pair<long double, long double> >)':
input/code.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)
              ~^~~~~~~~~
input/code.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<b.size();j++)
               ~^~~~~~~~~
input/code.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<nw.size();i++)
              ~^~~~~~~~~~

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef pair<ld,ld> interval;

interval cross(interval a, interval b)
{
	interval nw = mp(max(a.fi,b.fi),min(a.se,b.se));
	if(nw.fi>nw.se) return mp(-1,-1);
	else return nw;
}

vector<interval> intersect(vector<interval> a, vector<interval> b)
{
	vector<interval> nw;
	for(int i=0;i<a.size();i++)
	{
		for(int j=0;j<b.size();j++)
		{
			interval x = cross(a[i],b[j]);
			if(x.fi<0) continue;
			nw.pb(x);
		}
	}
	if(nw.empty()) return {};
	sort(nw.begin(),nw.end());
	ld l=nw[0].fi; ld r=nw[0].se;
	vector<interval> res;
	for(int i=1;i<nw.size();i++)
	{
		ld L = nw[i].fi;
		ld R = nw[i].se;
		if(L>r)
		{
			res.pb(mp(l,r));
			l=L; r=R;
		}
		else
		{
			r=max(r,R);
		}
	}
	res.pb(mp(l,r));
	return res;
}
const ld eps=ld(1e-15);
ld PI=acos(-1);
void solve()
{
	int n; cin>>n;
	vector<ii> vec; 
	for(int i=0;i<n;i++)
	{
		int x,y; cin>>x>>y;
		vec.pb(mp(x,y));
	}
	for(int sign=0;sign<2;sign++)
	{
		vector<interval> V;
		V.pb({0,PI*0.5-eps});
		for(int i=1;i<n;i++)
		{
			ll dx = vec[i-1].fi-vec[i].fi;
			ll dy = vec[i-1].se-vec[i].se;
			vector<interval> nw;
			//check 0,pi/2
			if(!sign)
			{
				if(dx<0) nw.pb({0,0});
			}
			else
			{
				if(dx>0) nw.pb({0,0});
			}
			if(dy==0) 
			{
				if(dx!=0)
				{
					if((dx<0)^(!sign)) 
					{
						nw.pb({0,PI*0.5-eps});
					}
				}
			}
			if(dx==0)
			{
				if(dy!=0)
				{
					if((dy>0)^(!sign))
					{
						nw.pb({eps,PI*0.5-eps});
					}
				}
			}
			//cerr<<"NW : "<<nw.size()<<'\n';
			if(dx!=0&&dy!=0)
			{
				ld ratio = ld(dx)/ld(dy);
				int s = sign;
				if(dy<0) s^=1;
				//0,PI/2
				//tan(a)>ratio
				{
					ld tmp = atan(ratio);
					tmp=max(tmp,ld(0));
					//cerr<<s<<' '<<tmp<<'\n';
					if(s) nw.pb({tmp+eps,PI*0.5-eps});
					else nw.pb({eps,tmp-eps});
				}
			}
			/*
			for(interval x:nw)
			{
				cerr<<fixed<<setprecision(10)<<x.fi<<' '<<x.se<<'\n';
			}
			cerr<<'\n';
			*/
			vector<interval> N = intersect(V,nw);
			V=N;
			/*
			for(interval x:N)
			{
				cerr<<fixed<<setprecision(10)<<x.fi<<' '<<x.se<<'\n';
			}
			cerr<<"END"<<'\n';
			*/
		}
		if(!V.empty()) {cout<<"YES\n"; return ;}
		//cerr<<"LOOP "<<sign<<" COMPLETE\n";
	}
	for(int sign=0;sign<2;sign++)
	{
		vector<interval> V;
		V.pb({0,PI*0.5-eps});
		for(int i=1;i<n;i++)
		{
			ll dx = vec[i-1].fi-vec[i].fi;
			ll dy = vec[i].se-vec[i-1].se;
			vector<interval> nw;
			//check 0,pi/2
			if(!sign)
			{
				if(dy>0) nw.pb({0,0});
			}
			else
			{
				if(dy<0) nw.pb({0,0});
			}
			if(dy==0) 
			{
				if(dx!=0)
				{
					if((dx<0)^(!sign)) 
					{
						nw.pb({0,PI*0.5-eps});
					}
				}
			}
			if(dx==0)
			{
				if(dy!=0)
				{
					if((dy>0)^(!sign))
					{
						nw.pb({eps,PI*0.5-eps});
					}
				}
			}
			//cerr<<"NW : "<<nw.size()<<'\n';
			if(dx!=0&&dy!=0)
			{
				ld ratio = ld(dy)/ld(dx);
				int s = sign;
				if(dx<0) s^=1;
				//0,PI/2
				//tan(a)>ratio
				{
					ld tmp = atan(ratio);
					tmp=max(tmp,ld(0));
					if(!s) nw.pb({tmp+eps,PI*0.5-eps});
					else nw.pb({eps,tmp-eps});
				}
			}
			vector<interval> N = intersect(V,nw);
			V=N;
			/*
			for(interval x:N)
			{
				cerr<<fixed<<setprecision(10)<<x.fi<<' '<<x.se<<'\n';
			}
			cerr<<"END"<<'\n';
			*/
		}
		if(!V.empty()) {cout<<"YES\n"; return ;}
	}
	cout<<"NO\n";
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin>>t;
	while(t--) solve();
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
12
2
0 0
1 1
5
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 2

Group: 1

Verdict: ACCEPTED

input
100
2
92 30
22 44
2
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 3

Group: 1

Verdict: ACCEPTED

input
100
3
-55 -98
-59 -55
-2 88
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 4

Group: 1

Verdict: ACCEPTED

input
100
4
87 81
-84 42
18 -46
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 5

Group: 1

Verdict: ACCEPTED

input
100
1000
-81 38
92 -21
-10 -65
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 6

Group: 1

Verdict: ACCEPTED

input
100
110
-99 -9
-98 -9
-96 -8
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 7

Group: 1

Verdict: ACCEPTED

input
100
78
-100 95
-99 96
-98 95
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 8

Group: 1

Verdict: ACCEPTED

input
100
201
-100 97
-100 96
-99 99
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 9

Group: 1

Verdict: ACCEPTED

input
100
45
-100 89
-100 90
-97 90
...

correct output
YES
NO
NO
NO
NO
...

user output
YES
NO
NO
NO
NO
...

Test 10

Group: 2

Verdict:

input
13
2
0 0
1 1
5
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 11

Group: 2

Verdict: ACCEPTED

input
100
2
-517113909 -39540276
-209411537 -831819487
2
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 12

Group: 2

Verdict: ACCEPTED

input
100
3
-991349544 139282777
646238126 16140762
-4488261 817588303
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 13

Group: 2

Verdict: ACCEPTED

input
100
4
891187584 -889373775
-453505448 -469134344
-683807769 8725517
...

correct output
YES
NO
YES
NO
NO
...

user output
YES
NO
YES
NO
NO
...

Test 14

Group: 2

Verdict: ACCEPTED

input
100
1000
-866614983 -994037153
775605588 -328510132
390868551 927606059
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 15

Group: 2

Verdict: ACCEPTED

input
100
1000
-911073332 -1000000000
-905159999 -1000000000
-904949593 -999999999
...

correct output
YES
YES
YES
NO
NO
...

user output
YES
YES
YES
NO
NO
...

Test 16

Group: 2

Verdict: ACCEPTED

input
100
1000
-1000000000 950042028
-946551105 -1000000000
-940508390 -1000000000
...

correct output
NO
YES
YES
YES
NO
...

user output
NO
YES
YES
YES
NO
...

Test 17

Group: 2

Verdict: ACCEPTED

input
100
1000
-949977239 -1000000000
-948279892 -1000000000
-947497811 -999999999
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 18

Group: 2

Verdict: ACCEPTED

input
100
806
-899 -1000
-898 -1000
-896 -999
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 19

Group: 2

Verdict: ACCEPTED

input
100
777
-1000 914
-1000 915
-999 916
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 20

Group: 2

Verdict: ACCEPTED

input
100
775
-999 998
-995 -1000
-994 -1000
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 21

Group: 2

Verdict:

input
13
2
0 0
1 1
5
...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 22

Group: 2

Verdict: ACCEPTED

input
1
999748
-995394098 -1000000000
-995392159 -1000000000
-995386584 -999999999
...

correct output
NO

user output
NO

Test 23

Group: 2

Verdict:

input
1
1000000
-954368893 -1000000000
-954366895 -1000000000
-954364896 -999999999
...

correct output
YES

user output
(empty)

Test 24

Group: 2

Verdict:

input
1
1000000
-1000000000 928772368
-1000000000 928772506
-999999999 928772642
...

correct output
YES

user output
(empty)

Test 25

Group: 2

Verdict: ACCEPTED

input
1
999754
-901705699 -1000000000
-901702695 -1000000000
-901702062 -999999999
...

correct output
NO

user output
NO

Test 26

Group: 2

Verdict: ACCEPTED

input
100
10000
-1000000000 919783772
-918885599 -1000000000
-918825263 -1000000000
...

correct output
NO
YES
YES
NO
NO
...

user output
NO
YES
YES
NO
NO
...

Test 27

Group: 2

Verdict:

input
10
99998
-997024120 -77018772
-997011201 -77017738
-996986132 -77015834
...

correct output
YES
YES
NO
YES
YES
...

user output
(empty)

Test 28

Group: 2

Verdict: ACCEPTED

input
100
7934
-10000 9905
-10000 9906
-9999 9906
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 29

Group: 2

Verdict: ACCEPTED

input
100
9710
-99754 -6983
-99786 -6055
-99751 -6548
...

correct output
YES
NO
NO
NO
NO
...

user output
YES
NO
NO
NO
NO
...

Test 30

Group: 2

Verdict: ACCEPTED

input
100
2
802396401 -641287652
30956766 -527704723
2
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 31

Group: 2

Verdict: ACCEPTED

input
100
3
755025461 -953536159
-402145543 137775005
-700733185 821755784
...

correct output
YES
YES
YES
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Test 32

Group: 2

Verdict: ACCEPTED

input
100
4
-673213071 571383249
-963633735 -859013318
-591788323 791136643
...

correct output
NO
NO
NO
NO
YES
...

user output
NO
NO
NO
NO
YES
...

Test 33

Group: 2

Verdict: ACCEPTED

input
100
5
-124483012 623794901
233757283 -234519096
-987338502 737259422
...

correct output
NO
NO
YES
NO
NO
...

user output
NO
NO
YES
NO
NO
...

Test 34

Group: 2

Verdict: ACCEPTED

input
100
1000
154383911 872030445
-9594726 190227899
908758769 -9615631
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 35

Group: 2

Verdict:

input
100
10000
642800667 -694556052
-343795089 -341227394
800920828 676674460
...

correct output
NO
NO
NO
NO
NO
...

user output
(empty)