QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96650 | #5155. Faster Than Light | Zuqa | WA | 2ms | 3452kb | C++20 | 6.7kb | 2023-04-14 23:22:03 | 2023-04-14 23:22:06 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
typedef unsigned long long ull;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
const ld eps = 1e-8;
const int PolygonCnt = 1 + 3;
#define int ll
#define X real()
#define Y imag()
#define vec(a, b) b - a
ld cross(point a, point b)
{
return ((conj(a) * (b)).imag());
}
ld dot(point a, point b)
{
return ((conj(a) * (b)).real());
}
int dcmp(ld a, ld b)
{
return fabs(a - b) <= eps ? 0 : a < b ? -1 : 1;
}
bool lexComp(const point &a, const point &b)
{
return a.X < b.X or (dcmp(a.X, b.X) == 0 and a.Y < b.Y);
}
int sign(ld val)
{
return (val > eps ? 1 : (val < -eps ? -1 : 0));
}
bool pointInTriangle(point a, point b, point c, point pt)
{
ld s1 = abs(cross(vec(a, b), vec(a, c)));
ld s2 = abs(cross(vec(pt, a), vec(pt, b))) + abs(cross(vec(pt, b), vec(pt, c))) +
abs(cross(vec(pt, c), vec(pt, a)));
return dcmp(s1, s2) == 0;
}
bool isPointOnSegment(point a, point b, point c)
{
ld acb = abs(a - b), ac = abs(a - c), cb = abs(b - c);
return dcmp(acb - (ac + cb), 0) == 0;
}
vector<point> seq[PolygonCnt];
point translation[PolygonCnt], polygonStart[PolygonCnt], polygonEnd[PolygonCnt];
int num[PolygonCnt];
/// todo: call pre
/// give polygon to answer queries on
void pre(vector<point> &points, int idx)
{
num[idx] = points.size();
int pos = 0;
for(int i = 1; i < num[idx]; i++)
if(lexComp(points[i], points[pos]))
pos = i;
rotate(points.begin(), points.begin() + pos, points.end());
num[idx]--;
seq[idx].resize(num[idx]);
for(int i = 0; i < num[idx]; i++)
seq[idx][i] = points[i + 1] - points[0];
translation[idx] = points[0];
polygonStart[idx] = points[0];
polygonEnd[idx] = points.back();
}
bool pointInConvexPolygon(point pt, int idx)
{ // inside or on
if(seq[idx].size() == 1)
return isPointOnSegment(polygonStart[idx], polygonEnd[idx], pt);
pt = pt - translation[idx];
if(dcmp(cross(seq[idx][0], pt), 1) != 0 and
sign(cross(seq[idx][0], pt)) != sign(cross(seq[idx][0], seq[idx][num[idx] - 1])))
return 0;
if(dcmp(cross(seq[idx][num[idx] - 1], pt), 0) != 0 and
sign(cross(seq[idx][num[idx] - 1], pt)) != sign(cross(seq[idx][num[idx] - 1], seq[idx][0])))
return 0;
if(dcmp(cross(seq[idx][0], pt), 0) == 0)
return dcmp(dot(seq[idx][0], seq[idx][0]), dot(pt, pt)) != -1;
int l = 0, r = num[idx] - 1;
while(r - l > 1)
{
int mid = (l + r) / 2;
int pos = mid;
if(dcmp(cross(seq[idx][pos], pt), 0) != -1)
l = mid;
else
r = mid;
}
int pos = l;
return pointInTriangle(seq[idx][pos], seq[idx][pos + 1], point(0, 0), pt);
}
bool pointOnPolygon(vector<point> &p, point pt)
{
int sz = p.size(), s, e, before = -1, after = -1, m;
s = 1, e = sz - 1;
while(s <= e)
{
m = (s + e) >> 1;
if(cross(vec(p[0], p[m]), vec(p[0], pt)) >= 0)
before = m, s = m + 1;
else
e = m - 1;
}
s = 1, e = sz - 1;
while(s <= e)
{
m = (s + e) >> 1;
if(cross(vec(p[0], pt), vec(p[0], p[m])) >= 0)
after = m, e = m - 1;
else
s = m + 1;
}
if(before == -1 or after == -1)
return 0;
if(before == after)
{
if(before == 1 or before == sz - 1)
return isPointOnSegment(p[0], p[before], pt);
else
return abs(p[before] - pt) < eps;
}
return isPointOnSegment(p[before], p[after], pt);
}
struct Point
{
ll x, y;
Point(ll x, ll y) : x(x), y(y)
{}
Point operator-(Point other)
{
return Point(x - other.x, y - other.y);
}
bool operator<(const Point &other) const
{
return x != other.x ? x < other.x : y < other.y;
}
};
ll cross(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}
ll dot(Point a, Point b)
{
return a.x * b.x + a.y * b.y;
}
struct sortCCW
{
Point center;
sortCCW(Point center) : center(center)
{}
bool operator()(Point a, Point b)
{
ll res = cross(a - center, b - center);
if(res)
return res > 0;
return dot(a - center, a - center) < dot(b - center, b - center);
}
};
vector<Point> hull(vector<Point> v)
{
sort(v.begin(), v.end());
sort(v.begin() + 1, v.end(), sortCCW(v[0]));
v.push_back(v[0]);
vector<Point> ans;
for(auto i: v)
{
int sz = ans.size();
while(sz > 1 && cross(i - ans[sz - 1], ans[sz - 2] - ans[sz - 1]) <= 0)
ans.pop_back(), sz--;
ans.push_back(i);
}
ans.pop_back();
return ans;
}
void doWork()
{
int n;
cin >> n;
vector<Point> h1, h2, h3, h4;
for(int i = 0, x1, y1, x2, y2, x3, y3, x4, y4; i < n; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
h1.emplace_back(x1, y1), h2.emplace_back(x2, y2);
x3 = x1, y3 = y2, x4 = x2, y4 = y1;
h3.emplace_back(x3, y3), h4.emplace_back(x4, y4);
}
h1 = hull(h1), h2 = hull(h2), h3 = hull(h3), h4 = hull(h4);
vector<point> v1, v3;
for(auto &it: h1)
v1.emplace_back(point(it.x, it.y));
for(auto &it: h3)
v3.emplace_back(point(it.x, it.y));
pre(v1, 0), pre(v3, 1);
bool ok = true;
for(auto it: h2)
{
if(pointOnPolygon(v1, point(it.x, it.y)))
continue;
ok &= !pointInConvexPolygon(point(it.x, it.y), 0);
}
if(ok)
return cout << "possible", void();
ok = true;
for(auto it: h4)
{
if(pointOnPolygon(v3, point(it.x, it.y)))
continue;
ok &= !pointInConvexPolygon(point(it.x, it.y), 1);
}
cout << (ok ? "possible" : "impossible");
}
signed main()
{
FIO
int T = 1;
// cin >> T;
for(int i = 1; i <= T; i++)
doWork();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3328kb
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: 2ms
memory: 3364kb
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: 3452kb
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: 2ms
memory: 3364kb
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'