QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201992 | #5155. Faster Than Light | nameless_story | RE | 0ms | 0kb | C++20 | 4.7kb | 2023-10-05 18:09:43 | 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