QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187720 | #6403. Master of Polygon | UESTC_Guest_WiFi | WA | 60ms | 3612kb | C++17 | 11.3kb | 2023-09-24 21:16:57 | 2023-09-24 21:16:57 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size) memset(array, value, ((size) + 5) * sizeof(decltype(array[0])))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v) (sort(vecall(v), greater<decltype(v.back())>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
#define vecunique(v) ((v).resize(unique(vecall(v)) - (v).begin()))
using namespace std;
using db = long long;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const db PI = acos(-1.0L);
const db eps = 1e-8;
int dcmp(const db x)
{
if (abs(x) <= eps)
return 0;
return x < 0 ? -1 : 1;
}
struct Point
{
db x, y;
Point() = default;
Point(db x, db y) : x(x), y(y) {}
bool operator==(const Point &a) const
{
return (abs(x - a.x) <= eps && abs(y - a.y) <= eps);
}
Point operator+(const Point &a) const { return Point(x + a.x, y + a.y); }
Point operator-(const Point &a) const { return Point(x - a.x, y - a.y); }
Point operator-() const { return Point(-x, -y); }
Point operator*(const db &k) const { return Point(k * x, k * y); }
Point operator/(const db &k) const { return Point(x / k, y / k); }
db operator*(const Point &a) const { return x * a.x + y * a.y; } // Dot
db operator^(const Point &a) const { return x * a.y - y * a.x; } // Cross
bool operator<(const Point &a) const
{
if (abs(x - a.x) <= eps)
return y < a.y - eps;
return x < a.x - eps;
}
bool is_par(const Point &a) const { return abs((*this) ^ a) <= eps; }
bool is_ver(const Point &a) const { return abs((*this) * a) <= eps; }
int toleft(const Point &a) const
{
auto t = (*this) ^ a;
return (t > eps) - (t < -eps);
}
db len() const { return sqrt((*this) * (*this)); }
db dis(const Point &a) const { return (a - (*this)).len(); }
db ang(const Point &a) const
{
return acos(((*this) * a) / (this->len() * a.len()));
}
Point rot(const db &rad) const
{
return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
}
Point rot(const db &cosr, const db &sinr) const
{
return {x * cosr - y * sinr, x * sinr + y * cosr};
} // 逆时针旋转(给定角度的正弦与余弦)
};
using vp = vector<Point>;
bool argcmp(const Point &a, const Point &b)
{
int ha = 0, hb = 0;
if (a.y < -eps || (abs(a.y) <= eps && a.x >= -eps))
ha = -1;
else
ha = 1;
if (b.y < -eps || (abs(b.y) <= eps && b.x >= -eps))
hb = -1;
else
hb = 1;
if (ha != hb)
return ha < hb;
auto t = (a == Point(0, 0) ? Point(1, 0) : a) ^ (b == Point(0, 0) ? Point(1, 0) : b);
if (abs(t) <= eps)
return a * a < b * b - eps;
return t > eps;
}
struct Line
{
Point p, v; // p+tv
Line() = default;
Line(Point p, Point v) : p(p), v(v) {}
bool operator==(const Line &a) const { return (v.is_par(a.v) && v.is_par(p - a.p)); }
bool is_par(const Line &a) const { return (v.is_par(a.v) && !v.is_par(p - a.p)); }
bool is_ver(const Line &a) const { return v.is_ver(a.v); }
bool is_on(const Point &a) const { return v.is_par(a - p); }
int toleft(const Point &a) const { return v.toleft(a - p); }
Point inter(const Line &a) const { return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v)); }
db dis(const Point &a) const { return abs(v ^ (a - p)) / v.len(); }
Point proj(const Point &a) const { return p + v * ((v * (a - p)) / (v * v)); }
bool operator<(const Line &a) const
{
if (abs(v ^ a.v) <= eps && v * a.v >= -eps)
return ((a.p - p) ^ v) > eps;
return argcmp(v, a.v);
}
};
using vl = vector<Line>;
struct Segment
{
Point a, b;
Segment() = default;
Segment(Point a, Point b) : a(a), b(b) {}
bool is_on(const Point &c) const
{
return c == a || c == b || ((c - a) * (b - c) >= -eps && dcmp((c-a)^(c-b))==0);
}
Point inter(const Segment &c) const { return Line(a, b - a).inter(Line(c.a, c.b - c.a)); }
bool is_cross(const Segment &c)
{
Point p = inter(c);
return (p - a) * (b - p) >= -eps && (p - c.a) * (c.b - p) >= -eps;
}
};
struct Polygon
{
vector<Point> p;
Polygon() = default;
Polygon(vp p) : p(std::move(p)) {}
inline size_t nxt(const size_t &i) const { return i == p.size() - 1 ? 0 : i + 1; }
inline size_t pre(const size_t &i) const { return i == 0 ? p.size() - 1 : i - 1; }
db C() const
{
db sum = 0;
for (size_t i = 0; i < p.size(); i++)
sum += p[i].dis(p[nxt(i)]);
return sum;
}
db S() const
{
db sum = 0;
for (size_t i = 0; i < p.size(); i++)
sum += p[i] ^ p[nxt(i)];
return abs(sum) / 2;
}
// 判断点是否在凸多边形内
// 复杂度 O(logn)
// -1 点在多边形边上 | 0 点在多边形外 | 1 点在多边形内
int is_in(const Point &a) const
{
const auto &p = this->p;
if (p.size() == 1)
return a == p[0] ? -1 : 0;
if (p.size() == 2)
return Segment(p[0], p[1]).is_on(a) ? -1 : 0;
if (a == p[0])
return -1;
if ((p[1] - p[0]).toleft(a - p[0]) == -1 || (p.back() - p[0]).toleft(a - p[0]) == 1)
return 0;
const auto cmp = [&](const Point &u, const Point &v)
{ return (u - p[0]).toleft(v - p[0]) == 1; };
const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
if (i == 1)
return Segment{p[0], p[i]}.is_on(a) ? -1 : 0;
if (i == p.size() - 1 && Segment{p[0], p[i]}.is_on(a))
return -1;
if (Segment{p[i - 1], p[i]}.is_on(a))
return -1;
return (p[i] - p[i - 1]).toleft(a - p[i - 1]) > 0;
}
pair<int, int> get_tan(const Point &a)
{
if (is_in(a) != 0)
return {-2, -2};
if (p.size() == 1)
return {0, 0};
int n = p.size(), l = 0, r = n;
int ansl = -1, ansr = -1;
auto isleft = [a, this](int i, int j) -> bool
{
return ((p[i] - a) ^ (p[j] - a)) > 0;
};
while (l < r)
{
int mid = l + (r - l) / 2;
if (isleft(mid, pre(mid)) && !isleft(nxt(mid), mid))
{
ansr = mid;
break;
}
if (isleft(nxt(mid), mid) && !isleft(nxt(nxt(mid)), nxt(mid)))
{
ansr = nxt(mid);
break;
}
if (isleft(nxt(l), l))
{
if (!isleft(nxt(mid), mid))
r = mid;
else if (isleft(mid, l))
l = mid;
else
r = mid;
}
else
{
if (isleft(nxt(mid), mid))
l = mid;
else if (isleft(mid, l))
r = mid;
else
l = mid;
}
}
l = 0, r = n;
while (l < r)
{
int mid = l + (r - l) / 2;
if (!isleft(mid, pre(mid)) && isleft(nxt(mid), mid))
{
ansl = mid;
break;
}
if (!isleft(nxt(mid), mid) && isleft(nxt(nxt(mid)), nxt(mid)))
{
ansl = nxt(mid);
break;
}
if (!isleft(nxt(l), l))
{
if (isleft(nxt(mid), mid))
r = mid;
else if (!isleft(mid, l))
l = mid;
else
r = mid;
}
else
{
if (!isleft(nxt(mid), mid))
l = mid;
else if (!isleft(mid, l))
r = mid;
else
l = mid;
}
}
return {ansl, ansr};
}
};
#define back1(x) x.back()
#define back2(x) *(x.rbegin() + 1)
// Andrew
Polygon convex(vector<Point> p)
{
vector<Point> st;
sort(p.begin(), p.end());
for (Point u : p)
{
while (st.size() > 1 && (back1(st) - back2(st)).toleft(u - back2(st)) <= 0)
st.pop_back();
st.push_back(u);
}
size_t k = st.size();
p.pop_back();
reverse(p.begin(), p.end());
for (Point u : p)
{
while (st.size() > k && (back1(st) - back2(st)).toleft(u - back2(st)) <= 0)
st.pop_back();
st.push_back(u);
}
st.pop_back();
return Polygon(st);
}
Polygon P;
vp ps;
int n, Q;
inline void solve()
{
cin >> n >> Q;
ps.resize(n);
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
ps[i - 1] = Point(x, y);
}
P = convex(ps);
while (Q--)
{
int qx1, qy1, qx2, qy2;
cin >> qx1 >> qy1 >> qx2 >> qy2;
Point qu = Point(qx1, qy1), qv = Point(qx2, qy2);
// case 1
int ku = P.is_in(qu), kv = P.is_in(qv);
if (ku == -1 || kv == -1 || ku + kv == 1)
{
cout << "YES\n";
continue;
}
if (ku == 1 && kv == 1)
{
cout << "NO\n";
continue;
}
// case 2
auto tu = P.get_tan(qu), tv = P.get_tan(qv);
map<int, int> vis;
vis[tu.first]++, vis[tu.second]--;
vis[tv.first]++, vis[tv.second]--;
if (tu.first > tu.second)
vis[n]--, vis[0]++;
if (tv.first > tv.second)
vis[n]--, vis[0]++;
int cnt = 0, _2 = false;
for(auto [pos, v] : vis)
{
cnt += v;
_2 = (_2 || (cnt >= 2));
}
if (_2)
{
cout << "NO2\n";
continue;
}
auto vs = qv - qu;
auto vl = P.p[tu.first] - qu, vr = P.p[tu.second] - qu;
if ((vl ^ vs) <= 0 && (vs ^ vr) <= 0)
cout << "YES\n";
else
cout << "NO3\n";
}
}
int main()
{
// #define MULTIPLE_CASE
#define CLOSE_IOS
#ifdef CLOSE_IOS
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
int Test = 1;
#ifdef MULTIPLE_CASE
#ifdef CLOSE_IOS
cin >> Test;
#else
scanf("%d", &Test);
#endif
#endif
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3520kb
input:
4 6 1 1 4 1 4 4 1 4 0 2 2 0 0 1 1 1 0 0 5 5 2 2 4 2 2 2 3 2 5 1 0 2
output:
YES YES YES YES NO YES
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: -100
Wrong Answer
time: 60ms
memory: 3612kb
input:
20 200000 8838 9219 12190 11292 15953 7581 16690 6159 21104 5484 8978 1076 4354 1065 1261 676 12684 14159 15469 22416 13493 28027 15531 26837 18253 26053 26444 24253 22160 19958 24879 12856 28793 22156 25300 10245 14749 15078 12946 13942 26544 28338 18806 21279 5592 29200 20935 25253 28189 17513 215...
output:
YES YES YES NO YES YES NO YES YES YES YES YES YES YES NO YES YES YES NO2 YES YES YES YES NO YES YES NO NO3 YES NO YES NO YES YES YES NO NO NO YES YES YES YES YES NO YES NO2 NO2 YES NO YES YES NO NO2 YES YES YES NO YES YES YES NO YES YES NO2 YES NO2 YES NO YES YES YES YES YES NO NO2 YES NO YES YES NO...
result:
wrong answer expected YES, found NO [4th token]