QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#746719#7906. Almost ConvexmobbbWA 1ms3812kbC++206.9kb2024-11-14 15:21:472024-11-14 15:21:50

Judging History

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

  • [2024-11-14 15:21:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3812kb
  • [2024-11-14 15:21:47]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long

#define db ll
constexpr db EPS = 0;
int sign(db a){ return a < -EPS ? -1 : a > EPS; }
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;}
    // a * b == |a| * |b| * cos<a,b>  ,大于0为锐角小于0为钝角等于0为直角
    db det(P p){return {x * p.y - y * p.x};}
    // a * b == |a| * |b| * sin<a,b> == - (b * a) ,a逆时针转多少度可以转到b
    // 大于0 b在a的逆时针方向,等于0共线,小于0 b在a的顺时针方向
    void read(){std::cin >> x >> y;}
    void print(){std::cout << x << " " << y  << "\n";}
    db distTo(P p) {return (*this - p).abs();}
    db alpha() {return atan2l(y,x);}
    db abs() {return sqrtl(abs2());}
    db abs2() {return x * x + y * y;}
    P rot90() {return P(-y,x);} // 逆时针旋转90度
    int quad(){return sign(y) == 1 || (sign(y) == 0 && sign(x) == 1);}
    P unit() {return *this / abs();}
    P rot(db an){return {x * cosl(an) - y * sinl(an),x * sinl(an) + y * cosl(an)};}
};
#define cross(p1,p2,p3) ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3)) // 以p1为起点去考虑<p1,p2> <p1,p3>
// 大于0 p3在p2的逆时针方向,小于0在顺时针,等于0共线

// 两个直线是否相交
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;
}
// 求两直线交点
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) std::swap(l1,r1);if (l2 > r2) std::swap(l2,r2);
    return !(cmp(r1,l2) == -1 || cmp(r2,l1) == -1);
}
// 两线段是否相交
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;
}
// 两线段是否严格相交
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){
    return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
// 点m 在不在a和b之间
bool isMiddle(P a,P m,P b){
    return isMiddle(a.x,m.x,b.x) && isMiddle(a.y,m.y,b.y);
}
// 点q在线段上
bool onSeg(P p1,P p2, P q){
    return crossOp(p1,p2,q) == 0 && isMiddle(p1,q,p2);
}
// 点q严格在线段上
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));
}
// 求 q 到 p1p2的投影
P proj(P p1,P p2,P q){
    P dir = p2 - p1;
    return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q以直线p1p2为轴的反射
P refect(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 std::min(p1.distTo(q),p2.distTo(q));
}
// 求线段p1p2 与线段q1q2的距离
db disSS(P p1,P p2,P q1,P q2){
    if(isSS(p1,p2,q2,q2)) return 0;
    return std::min({nearest(p1,p2,q1),nearest(p1,p2,q2),nearest(q1,q2,p1),nearest(q1,q2,p2)});
}
// 极角排序
// sort(p.begin(), p.end(), [&](P a, P b){
// 	int qa = a.quad(),qb = b.quad();
// 	if (qa != qb) return qa < qb;
// 	return sign(a.det(b)) > 0;
// })
std::vector<P> convexHull(std::vector<P> ps){ // need unique , <= strict , < strict
    int n = ps.size();
    if (n <= 1) return ps;
    std::sort(ps.begin(), ps.end());
    std::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;
}

db area(std::vector<P> ps){
    db ans = 0;
    for (int i = 0;i < ps.size();i++){
        ans += ps[i].det(ps[(i + 1) % (ps.size())]);
    }
    ans /= 2;
    return ans;
}

// bool check(std::vector<P> p){
// 	int n = p.size();
// 	bool ok = true;
// 	double angle = 0;
// 	for (int i = 0; i < n; i++){
// 		P L = p[i] - p[(i - 1 + n) % n];
// 		P R = p[(i + 1) % n] - p[i];
// 		if (L.det(R) <= 0 || L == P(0, 0) || R == P(0, 0)){
// 			ok = false;
// 		}
// 	}
// 	return ok;
// }

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;

    std::cin >> n;
    std::vector<P> p(n);

    for (int i = 0; i < n; i++){
        p[i].read();
    }
    auto Hull = convexHull(p);
    std::map<P, int> cnt;
    for (int i = 0; i < Hull.size(); i++){
        cnt[Hull[i]] = 1;
    }
    // assert(check(Hull));
    std::vector<P> inside;
    for (int i = 0; i < n; i++){
        if (cnt.find(p[i]) == cnt.end()){
            inside.push_back(p[i]);
        }
    }
    inside = convexHull(inside);
    int m = Hull.size(), k = inside.size();
    // for (int i = 0; i < m; i++){
    // 	Hull[i].print();
    // }
    int ans = 1;
    // std::cout << k << '\n';
    if (inside.empty()){
        std::cout << ans << '\n';
        return 0;
    }
    // for (auto x : inside){
    //     x.print();
    // }
    for (int i = 0; i < m; i++){
        P p1 = Hull[i], p2 = Hull[(i + 1) % m];
        std::vector<P> s(k);
        int l = 0, r = -1, x = 0;
        auto check1 = [=](P L, P R, P mid){
            return (L.det(mid) > 0 && R.det(mid) < 0);
        };
        auto check2 = [=](P L, P R, P mid){
            return (L.det(mid) < 0 && R.det(mid) <= 0);
        };
        for (int j = 0; j < k; j++){
            x = std::max(x, j + 1);
            x %= k;
            while (check1(p1 - inside[j], p2 - inside[j], inside[x] - inside[j]) && r - l + 1 < k){
                s[++r] = inside[x];
                x = (x + 1) % k;
            }
            if (r - l + 1 == 0){
                ans++;
            }
            while (l <= r && check2(inside[j] - p1, inside[(j + 1) % k] - p1, s[r] - p1)){
                l++;
            }
        }
        // std::cerr << ans << '\n';
    }
    std::cout << ans << '\n';

    return 0;
}

详细

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3656kb

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:

1687

result:

wrong answer 1st numbers differ - expected: '718', found: '1687'