QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201698#5155. Faster Than Lightnameless_story#WA 1ms3516kbC++203.1kb2023-10-05 16:13:512023-10-05 16:13:51

Judging History

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

  • [2023-10-05 16:13:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3516kb
  • [2023-10-05 16:13:51]
  • 提交

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";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3456kb

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: 3516kb

input:

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

output:

possible

result:

ok single line: 'possible'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3440kb

input:

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

output:

possible

result:

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