QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250726#7693. Convex Hull ExtensionfunnufWA 1ms3640kbC++175.2kb2023-11-13 16:09:342023-11-13 16:09:35

Judging History

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

  • [2023-11-13 16:09:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3640kb
  • [2023-11-13 16:09:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rep(i, j, k) for (ll i = j; i <= k; ++i)
#define per(i, j, k) for (ll i = j; i >= k; --i)
#define closeSync            \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)
#define pii pair<ll, ll>
#define fi first
#define se second
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

#define double long double
#define int long long

const double eps = 1e-8;

struct Point {
    double x, y;
    Point() {
    }
    Point(double x, double y) :
        x(x), y(y) {
    }
    bool operator<(const Point &it) {
        if (abs(x - it.x) >= eps) return x < it.x;
        if (abs(y - it.y) >= eps) return y < it.y;
        return 0;
    }
};
typedef Point Vector;

Vector operator+(Point A, Point B) {
    return Vector(A.x + B.x, A.y + B.y);
}

Vector operator-(Point A, Point B) {
    return Vector(A.x - B.x, A.y - B.y);
}

Vector operator*(Vector A, double p) {
    return Vector(A.x * p, A.y * p);
}

Vector operator/(Vector A, double p) {
    return Vector(A.x / p, A.y / p);
}

double Dot(Vector A, Vector B) {
    return A.x * B.x + A.y * B.y;
}

double Length(Vector A) {
    return sqrt(Dot(A, A));
}

double Cross(Vector A, Vector B) { // 叉积
    return A.x * B.y - A.y * B.x;
}

int dcmp(double x) {
    if (abs(x) < eps)
        return 0;
    else if (x < 0)
        return -1;
    return 1;
}

double DistanceDotToLine(Point P, Point A, Point B) {
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2) / Length(v1));
}

Point GedLineIntersection(Point P, Vector v, Point Q, Vector w) { // 交点
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

Point P[55];

int n;
int pre(int x) {
    if (x == 1) return n;
    return x - 1;
}
int aft(int x) {
    if (x == n) return 1;
    return x + 1;
}

int _ceil(double x) {
    int xx = ceil(x);
    if (abs(x - (xx - 1)) < eps) return xx - 1;
    return xx;
}
int _floor(double x) {
    int xx = floor(x);
    if (abs(x - (xx + 1)) < eps) return xx + 1;
    return xx;
}

int cal(Point A, Point B, Point C) {
    int res = 0;
    // Point lb = {min({A.x, B.x, C.x}), min({A.y, B.y, C.y})};
    // Point rt = {max({A.x, B.x, C.x}), max({A.y, B.y, C.y})};
    vector<Point> vec;
    vec.push_back(A);
    vec.push_back(B);
    vec.push_back(C);
    sort(vec.begin(), vec.end());
    A = vec[0];
    B = vec[1];
    C = vec[2];

    if (abs(B.x - C.x) < eps) {
        A.x = 2 * B.x - A.x;
        Point tmp = A;
        A = B;
        B = C;
        C = tmp;
    }

    if (abs(A.x - B.x) < eps) {
        Point pb = A, pc = A;
        double dy_AC = (C.y - A.y) / (C.x - A.x);
        double dy_AB = (B.y - A.y) / (B.x - A.x);
        pb.y -= abs(A.x - _floor(A.x)) * dy_AB;
        pc.y -= abs(A.x - _floor(A.x)) * dy_AC;

        rep(i, _floor(A.x) + 1, _floor(C.x)) {
            pb.y += dy_AB;
            pc.y += dy_AC;
            double tp = max(pb.y, pc.y);
            double bt = min(pb.y, pc.y);
            res += (_ceil(tp) - 1) - (_floor(bt) + 1) + 1;
        }
    } else {
        // cout << A.x << " " << A.y << " -- A\n";
        // cout << B.x << " " << B.y << " -- B\n";
        // cout << C.x << " " << C.y << " -- C\n";
        Point pb = A, pc = A;
        double dy_AC = (C.y - A.y) / (C.x - A.x);
        double dy_AB = (B.y - A.y) / (B.x - A.x);
        // cout << dy_AC << " " << dy_AB << "\n";
        pb.y -= abs(A.x - _floor(A.x)) * dy_AB;
        pc.y -= abs(A.x - _floor(A.x)) * dy_AC;

        // cout << pb.y << " " << pc.y << "\n";

        rep(i, _floor(A.x) + 1, _floor(B.x)) {
            // cout << i << "\n";
            pb.y += dy_AB;
            pc.y += dy_AC;
            double tp = max(pb.y, pc.y);
            double bt = min(pb.y, pc.y);
            res += (_ceil(tp) - 1) - (_floor(bt) + 1) + 1;
            // cout << "case1: " << i << " " << bt << " " << tp << " " << (_ceil(tp) - 1) - (_floor(bt) + 1) + 1 << " " << _ceil(tp) << " " << _floor(bt) << "\n";
        }
        pb = B;
        double dy_BC = (C.y - B.y) / (C.x - B.x);
        pb.y -= abs(B.y - _floor(B.y)) * dy_BC;
        rep(i, _floor(B.x) + 1, _ceil(C.x) - 1) {
            // cout << i << "\n";
            pc.y += dy_AC;
            pb.y += dy_BC;
            double tp = max(pb.y, pc.y);
            double bt = min(pb.y, pc.y);
            res += (_ceil(tp) - 1) - (_floor(bt) + 1) + 1;
            // cout << "case2: " << i << " " << bt << " " << tp << " " << (_ceil(tp) - 1) - (_floor(bt) + 1) + 1 << "\n";
        }
    }
    return res;
}

void solve() {
    cin >> n;
    rep(i, 1, n) {
        cin >> P[i].x >> P[i].y;
    }
    ll ans = 0;
    rep(i, 1, n) {
        int p1 = pre(i);
        int p2 = aft(i);
        if (Cross(P[p1] - P[i], P[aft(p2)] - P[p2]) >= 0) {
            cout << "infinitely many";
            return;
        }
        Point Q = GedLineIntersection(P[i], P[p1] - P[i], P[p2], P[aft(p2)] - P[p2]);
        ans += cal(P[i], P[p2], Q);
    }
    cout << ans;
}

signed main() {
    closeSync;
    // int T;cin>>T;while(T--)
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

input:

5
0 2
-2 0
-1 -3
1 -3
2 1

output:

23

result:

ok single line: '23'

Test #2:

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

input:

4
-7 -7
7 -7
7 7
-7 7

output:

infinitely many

result:

ok single line: 'infinitely many'

Test #3:

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

input:

4
-1000 1000
-1000 999
-999 999
-999 1000

output:

infinitely many

result:

wrong answer 1st lines differ - expected: '0', found: 'infinitely many'