QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201992#5155. Faster Than Lightnameless_storyRE 0ms0kbC++204.7kb2023-10-05 18:09:432023-10-05 18:09:43

Judging History

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

  • [2023-10-05 18:09:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-05 18:09:43]
  • 提交

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)
		{
			auto cc=b;
			auto e=b;
			// for (auto [x,y]:a) cerr<<"("<<x<<", "<<y<<")\n"; cerr<<endl;
			// for (auto [x,y]:b) cerr<<"("<<x<<", "<<y<<")\n"; cerr<<endl;
			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);
			}
			swap(b,e);
			for (auto &[x,y]:b) x=-x,y=-y;
			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);
			}
			for (auto &[x,y]:b) x=-x,y=-y;
			swap(b,e);
			m=b.size();
			assert(b.size()+e.size()>=cc.size());
			// for (auto [x,y]:b) cerr<<"("<<x<<", "<<y<<")\n"; cerr<<endl;
			// for (auto [x,y]:e) cerr<<"("<<x<<", "<<y<<")\n"; cerr<<endl;
			for (i=0; i<n; i++)
			{
				if (0)
				{
					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;
					// cerr<<sgn<<endl;
					assert(sgn);
					if (sgn<0) sgn=-1; else sgn=1;
					bool flg=1;
					for (Q o:cc)
					{
						ll D=(o&d)-C;
						if (D)
						{
							if (D<0) D=-1; else D=1;
						}
						if (D==sgn) { flg=0; break; }
					}
					if (flg) return 1;
					continue;
				}
				// cerr<<i<<' '<<a[i].x<<' '<<a[i].y<<' '<<a[i+1].x<<' '<<a[i+1].y<<endl;
				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;
				// cerr<<sgn<<endl;
				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;
				// cerr<<D<<endl;rf
				if (D)
				{
					if (D<0) D=-1; else D=1;
				}
				if (D==sgn) continue;
				int q=e.size();
				l=0,r=q-1,mid;
				while (l<r)
				{
					mid=l+r>>1;
					if (((e[mid]&d)-(e[mid+1]&d))*sgn<0) l=mid+1;
					else r=mid;
				}
				D=(e[l]&d)-C;
				// cerr<<D<<' '<<sgn<<' '<<d.x<<' '<<d.y<<endl;
				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: 0
Runtime Error

input:

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

output:


result: