QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201716#5155. Faster Than Lightnameless_story#WA 91ms21804kbC++203.1kb2023-10-05 16:23:562023-10-05 16:23:56

Judging History

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

  • [2023-10-05 16:23:56]
  • 评测
  • 测评结果:WA
  • 用时:91ms
  • 内存:21804kb
  • [2023-10-05 16:23:56]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
struct Q
{
	ll x,y;
	Q operator+(const Q &o) const { return {x+o.x,y+o.y}; }
	Q operator-(const Q &o) const { return {x-o.x,y-o.y}; }
	ll operator*(const Q &o) const { return x*o.y-y*o.x; }
	ll operator&(const Q &o) const { return x*o.x+y*o.y; }
	bool operator!=(const Q &o) const { return x!=o.x||y!=o.y; }
	Q &operator+=(const Q &o) { x+=o.x; y+=o.y; return *this; }
	ll len2() const { return x*x+y*y; }
};
bool operator<(const Q &a,const Q &b)
{
	ll s=a*b;
	return s>0||s==0&&a.len2()<b.len2();
}
struct convex
{
	vector<Q> p;
	convex(vector<Q> a)
	{
		int n=a.size(),i;
		if (!n) return;
		p=a;
		for (i=1; i<n; i++) if (p[i].x<p[0].x||p[i].x==p[0].x&&p[i].y<p[0].y) swap(p[0],p[i]);
		a.resize(0); a.reserve(n);
		for (i=1; i<n; i++) if (p[i]!=p[0]) a.push_back(p[i]-p[0]);
		sort(all(a));
		for (i=0; i<a.size(); i++) a[i]+=p[0];
		Q *st=p.data()-1;
		int tp=1;
		for (auto &v:a)
		{
			while (tp>1&&(st[tp]-st[tp-1])*(v-st[tp-1])<=0) --tp;
			st[++tp]=v;
		}
		p.resize(tp);
	}
};
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cout<<fixed<<setprecision(15);
	int n,i;
	cin>>n;
	vector<array<ll,4>> axis(n);
	for (auto &[x1,y1,x2,y2]:axis) cin>>x1>>y1>>x2>>y2;
	auto sol2=[&](vector<Q> a,vector<Q> b)
		{
			n=a.size();
			a.push_back(a[0]);
			int m=b.size();
			sort(all(b),[&](Q a,Q b) { return a.x==b.x?a.y<b.y:a.x<b.x; });
			{
				vector<Q> c={b[0]};
				b.erase(b.begin());
				int tp=0;
				for (Q o:b)
				{
					if (c[tp].y<=o.y) continue;
					while (tp>=1&&(o-c[tp-1])*(c[tp]-c[tp-1])>=0)
					{
						--tp;
						c.pop_back();
					}
					c.push_back(o);
					++tp;
				}
				swap(b,c);
			}
			m=b.size();
			for (i=0; i<n; i++)
			{
				auto d=a[i+1]-a[i];
				swap(d.x,d.y); d.y=-d.y;
				ll C=d&a[i];
				auto o=a[(i+n-1)%n];
				ll sgn=(d&o)-C;
				assert(sgn);
				if (sgn<0) sgn=-1; else sgn=1;
				int l=0,r=m-1,mid;
				while (l<r)
				{
					mid=l+r>>1;
					if (((b[mid]&d)-(b[mid+1]&d))*sgn<0) l=mid+1;
					else r=mid;
				}
				ll D=(b[l]&d)-C;
				if (D)
				{
					if (D<0) D=-1; else D=1;
				}
				if (D!=sgn) return 1;
			}
			return 0;
		};
	auto solve=[&](const vector<array<ll,4>> &axis) -> bool
		{
			int n=axis.size(),i,j;
			vector<Q> a(n),b(n);
			for (i=0; i<n; i++) a[i]={axis[i][0],axis[i][1]};
			for (i=0; i<n; i++) b[i]={axis[i][2],axis[i][3]};
			a=convex(a).p;
			b=convex(b).p;
			if (a.size()<=2||b.size()<=2) return 1;
			if (sol2(a,b)) return 1;
			for (auto &[x,y]:a) x=-x,y=-y;
			for (auto &[x,y]:b) x=-x,y=-y;
			return sol2(b,a);
		};
	if (solve(axis))
	{
		cout<<"possible\n";
		return 0;
	}
	else
	{
		for (auto &[x1,y1,x2,y2]:axis) swap(x1,x2),x1=-x1,x2=-x2;
		if (solve(axis)) cout<<"possible\n";
		else cout<<"impossible\n";
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3800kb

input:

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4
1 1 2 2
1 3 2 4
3 1 4 2
3 3 4 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4
0 1 1 1000000000
1 0 999999999 1
999999999 0 1000000000 999999999
2 999999999 999999999 1000000000

output:

possible

result:

ok single line: 'possible'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 999999999 1000000000

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 1000000000 1000000000

output:

possible

result:

ok single line: 'possible'

Test #8:

score: -100
Wrong Answer
time: 91ms
memory: 21804kb

input:

199999
433914929 216935871 433914930 216935872
621822279 310889546 621822280 310889547
395914333 197935573 395914334 197935574
582775641 291366227 582775642 291366228
658726133 329341473 658726134 329341474
71689261 35823037 71689262 35823038
453260967 226608890 453260968 226608891
249802825 1248798...

output:

possible

result:

wrong answer 1st lines differ - expected: 'impossible', found: 'possible'