QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293118#7906. Almost ConvexSy03TL 0ms4112kbC++208.5kb2023-12-28 21:53:102023-12-28 21:53:11

Judging History

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

  • [2023-12-28 21:53:11]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4112kb
  • [2023-12-28 21:53:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 10;
const int mod = 1000000007;
#define inl inline
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
#define forall(i, a) for (auto &i : a)

/**
   ____         ___ _____
  / ___| _   _ / _ \___ /
  \___ \| | | | | | ||_ \
   ___) | |_| | |_| |__) |
  |____/ \__, |\___/____/
         |___/
*/
istream &operator>>(istream &in, vector<int> &v)
{
    for (auto &i : v)
        in >> i;
    return in;
}
ostream &operator<<(ostream &out, vector<int> &v)
{
    for (auto &i : v)
        out << i << " ";
    return out;
}
bool _output = 0;

#include <bits/stdc++.h>
using namespace std;

typedef long long db;
const db EPS = 1e-9;

inline int sign(db a)
{
    return a < -EPS ? -1 : a > EPS;
}

inline int cmp(db a, db b)
{
    return sign(a - b);
}

struct P
{
    db x, y;
    P() {}
    P(db _x, db _y) : x(_x), y(_y) {}
    // 重构加减乘除
    P operator+(P p) { return {x + p.x, y + p.y}; }
    P operator-(P p) { return {x - p.x, y - p.y}; }
    P operator*(db d) { return {x * d, y * d}; }
    P operator/(db d) { return {x / d, y / d}; }

    bool operator<(P p) const
    {
        int c = cmp(x, p.x);
        if (c)
            return c == -1;
        return cmp(y, p.y) == -1;
    }

    bool operator==(P o) const { return cmp(x, o.x) == 0 && cmp(y, o.y) == 0; }

    db dot(P p) { return x * p.x + y * p.y; } // 点积
    db det(P p) { return x * p.y - y * p.x; } // 叉积

    db distTo(P p) { return (*this - p).abs(); }
    db alpha() { return atan2(y, x); }
    void read() { cin >> x >> y; }
    void write() { cout << "(" << x << "," << y << ")" << endl; }
    db abs() { return sqrt(abs2()); }
    db abs2() { return x * x + y * y; }
    P rot90() { return P(-y, x); }
    P unit() { return *this / abs(); }
    int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
    P rot(db an)
    {
        return {0, 0};
    }
};

#define cross(p1, p2, p3) \
    ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
#define crossOp(p1, p2, p3) sign(cross(p1, p2, p3))

// 直线 p1p2, q1q2 是否恰有一个交点
bool chkLL(P p1, P p2, P q1, P q2)
{
    db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return sign(a1 + a2) != 0;
}

// 求直线 p1p2, q1q2 的交点
P isLL(P p1, P p2, P q1, P q2)
{
    db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return (p1 * a2 + p2 * a1) / (a1 + a2);
}

// 判断区间 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1, db r1, db l2, db r2)
{
    if (l1 > r1)
        swap(l1, r1);
    if (l2 > r2)
        swap(l2, r2);
    return !(cmp(r1, l2) == -1 || cmp(r2, l1) == -1);
}

// 线段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2)
{
    return intersect(p1.x, p2.x, q1.x, q2.x) &&
           intersect(p1.y, p2.y, q1.y, q2.y) &&
           crossOp(p1, p2, q1) * crossOp(p1, p2, q2) <= 0 &&
           crossOp(q1, q2, p1) * crossOp(q1, q2, p2) <= 0;
}

// 线段 p1p2, q1q2 严格相交
bool isSS_strict(P p1, P p2, P q1, P q2)
{
    return crossOp(p1, p2, q1) * crossOp(p1, p2, q2) < 0 &&
           crossOp(q1, q2, p1) * crossOp(q1, q2, p2) < 0;
}

// m 在 a 和 b 之间
bool isMiddle(db a, db m, db b)
{
    /*if (a > b) swap(a, b);
    return cmp(a, m) <= 0 && cmp(m, b) <= 0;*/
    return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}

bool isMiddle(P a, P m, P b)
{
    return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}

// 点 p 在线段 p1p2 上
bool onSeg(P p1, P p2, P q)
{
    return crossOp(p1, p2, q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交点 在 p1p2 上?

// 点 p 严格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q)
{
    return crossOp(p1, p2, q) == 0 &&
           sign((q - p1).dot(p1 - p2)) * sign((q - p2).dot(p1 - p2)) < 0;
}

// 求 q 到 直线p1p2 的投影(垂足) ⚠️ : p1 != p2
P proj(P p1, P p2, P q)
{
    P dir = p2 - p1;
    return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}

// 求 q 以 直线p1p2 为轴的反射
P reflect(P p1, P p2, P q)
{
    return proj(p1, p2, q) * 2 - q;
}

// 求 q 到 线段p1p2 的最小距离
// db nearest(P p1, P p2, P q)
// {
//     if (p1 == p2)
//         return p1.distTo(q);
//     P h = proj(p1, p2, q);
//     if (isMiddle(p1, h, p2))
//         return q.distTo(h);
//     return min(p1.distTo(q), p2.distTo(q));
// }

// // 求 线段p1p2 与 线段q1q2 的距离
// db disSS(P p1, P p2, P q1, P q2)
// {
//     if (isSS(p1, p2, q1, q2))
//         return 0;
//     return min(min(nearest(p1, p2, q1), nearest(p1, p2, q2)),
//                min(nearest(q1, q2, p1), nearest(q1, q2, p2)));
// }

// 极角排序

// sort(p, p + n, [&](P a, P b)
//      {
//     int qa = a.quad(), qb = b.quad();
//     if (qa != qb)
//         return qa < qb;
//     else
//         return sign(a.det(b)) > 0; });

const db eps = 1e-8;
struct argcmp
{
    bool operator()(P &a, P &b) const
    {
        const auto quad = [](const P &a)
        {
            if (a.y < -eps)
                return 1;
            if (a.y > eps)
                return 4;
            if (a.x < -eps)
                return 5;
            if (a.x > eps)
                return 3;
            return 2;
        };
        const int qa = quad(a), qb = quad(b);
        if (qa != qb)
            return qa < qb;
        db t = a.det(b);
        // if (abs(t)<=eps) return a*a<b*b-eps;  // 不同长度的向量需要分开
        return t > eps;
    }
};

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)

// 求多边形面积
db area(vector<P> ps)
{
    db ret = 0;
    rep(i, 0, ps.size()) ret += ps[i].det(ps[(i + 1) % ps.size()]);
    return ret / 2;
}
// 点包含
int contain(vector<P> ps, P p)
{ // 2:inside,1:on_seg,0:outside
    int n = ps.size(), ret = 0;
    rep(i, 0, n)
    {
        P u = ps[i], v = ps[(i + 1) % n];
        if (onSeg(u, v, p))
            return 1;
        if (cmp(u.y, v.y) <= 0)
            swap(u, v);
        if (cmp(p.y, u.y) > 0 || cmp(p.y, v.y) <= 0)
            continue;
        ret ^= crossOp(p, u, v) > 0;
    }
    return ret * 2;
}
// 严格凸包
vector<P> convexHull(vector<P> ps)
{
    int n = ps.size();
    if (n <= 1)
        return ps;
    sort(ps.begin(), ps.end());
    vector<P> qs(n * 2);
    int k = 0;
    for (int i = 0; i < n; qs[k++] = ps[i++])
        while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
            --k;
    for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
        while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
            --k;
    qs.resize(k - 1);
    return qs;
}

void solve()
{
    int n;
    cin >> n;
    vector<P> ps;
    fr(i, 1, n)
    {
        P p;
        cin >> p.x >> p.y;
        ps.push_back(p);
    }
    auto cv = convexHull(ps);
    set<pii> on_convex;
    for (auto now : cv)
    {
        on_convex.insert({now.x, now.y});
    }
    vector<P> inside;
    for (int i = 0; i < n; i++)
    {
        if (contain(cv, ps[i]) == 2)
        {
            inside.push_back(ps[i]);
        }
    }
    if (inside.size() == 0)
    {
        cout << "1" << endl;
        return;
    }
    // cout << inside.size() << endl;
    int ans = 0;
    for (auto now : inside)
    {
        // cout << now.x << " " << now.y << " ";
        vector<P> t;
        for (int i = 0; i < n; i++)
        {
            if (ps[i] == now)
                continue;
            t.push_back(ps[i]);
        }
        sort(t.begin(), t.end(), [&](P A, P B)
             { return atan2(A.y - now.y, A.x - now.x) < atan2(B.y - now.y, B.x - now.x); });
        int sz = t.size();
        for (int i = 0; i < sz; i++)
        {
            bool t1 = on_convex.count({t[i % sz].x, t[i % sz].y});
            bool t2 = on_convex.count({t[(i + 1) % sz].x, t[(i + 1) % sz].y});
            if (t1 && t2)
            {
                ans++;
            }
        }
        // cout << ans << endl;
    }
    cout << ans + 1 << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    if (_output)
        cin >> _;
    while (_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3964kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:


result: