QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96649#5155. Faster Than LightZuqaWA 2ms3432kbC++206.6kb2023-04-14 23:21:212023-04-14 23:21:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-14 23:21:24]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3432kb
  • [2023-04-14 23:21:21]
  • 提交

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 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: 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: 2ms
memory: 3384kb

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: 2ms
memory: 3364kb

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

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'