QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#454894#7730. Convex CheckerNephrennWA 0ms3940kbC++205.0kb2024-06-25 16:17:272024-06-25 16:17:27

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-06-25 16:17:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3940kb
  • [2024-06-25 16:17:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int MAXN = 1e2 + 10;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;

random_device seed;
mt19937 rnd(seed());
mt19937_64 rnd_64(seed());

const double eps = 1e-9;

int sgn(const double &x) {
    return x < -eps ? -1 : (x > eps ? 1 : 0);
}

double sqr(const double &x) {
    return x * x;
}

struct Point {
    double x, y;
    Point operator * (const double &k) {
        return {x * k, y * k};
    }
    Point operator / (const double &k) {
        return {x / k, y / k};
    }
    Point operator + (const Point &a) {
        return {x + a.x, y + a.y};
    }
    Point operator - (const Point &a) {
        return {x - a.x, y - a.y};
    }
    bool operator < (const Point &a) {
        // return y == a.y ? x < a.x : y < a.y;
        return x == a.x ? y < a.y : x < a.x;
    }
};

istream &operator >> (istream &is, Point &p) {
    is >> p.x >> p.y;
    return is;
}

bool operator < (const Point &a, const Point &b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

bool operator == (const Point &a, const Point &b) {
    return a.x == b.x && a.y == b.y;
}

double dis(const Point &a, const Point &b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

double det(const Point &a, const Point &b) {
    return a.x * b.y - b.x * a.y;
}
double det(const Point &a, const Point &b, const Point &c) {
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}

double dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}
double dot(const Point &a, const Point &b, const Point &c) {
    return (a.x - b.x) * (c.x - b.x) + (a.y - b.y) * (c.y - b.y);
}

struct Line {
    Point s, t;
};

bool point_on_segment(Point &a, Line &l) {
    return sgn(det(l.s - a, a - l.t)) == 0 && sgn(dot(l.s - a, a - l.t)) >= 0;
}

bool two_side(Point &a, Point &b, Line &c) {
    return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}

bool inter_judge(Line &a, Line &b) {
    if(point_on_segment(b.s, a) || point_on_segment(b.t, a) || point_on_segment(a.s, b) || point_on_segment(a.t, b)) {
        return true;
    }
    return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}

Point line_intersect(Line &a, Line &b) {
    double u = det(a.t - a.s, b.s - a.s);
    double v = -det(a.t - a.s, b.t - a.s);
    return (b.s * v + b.t * u) / (v + u);
}

double point_to_line(Point &p, Line &l) {
    return abs(det(l.t - l.s, p - l.s)) / dis(l.s, l.t);
}

double point_to_segment(Point &p, Line &l) {
    if(sgn(dot(l.s - p, l.t - l.s)) * sgn(dot(l.t - p, l.t - l.s)) <= 0) {
        return point_to_line(p, l);
    }
    return min(dis(p, l.s), dis(p, l.t));
}

double area(vector<Point> &a) {
    double res = 0;
    for(int i = 0; i < a.size(); ++i) {
        int j = (i + 1) % a.size();
        res += det(a[i], a[j]);
    }
    return res / 2.0;
}

bool turn_left(Point &a, Point &b, Point &c) {
    return sgn(det(b - a, c - a)) > 0;
}

bool same_dir(Line &a, Line &b) {
    return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}

vector<Point> convex_hull_Graham(vector<Point> a) {
    if(a.size() <= 2) return {}; // 或 return a;
    Point base = *min_element(a.begin(), a.end());
    sort(a.begin(), a.end(), [&](auto u, auto v) {
        int s = sgn(det(u - base, v - base));
        if(s) return s > 0;
        else return sgn(dis(u, base) - dis(v, base)) < 0;
    });
    
    vector<Point> res;
    for(auto i : a) {
        while(res.size() > 1 && !turn_left(res[res.size() - 2], res[res.size() - 1], i)) {
            res.pop_back();
        }
        res.push_back(i);
    }
    return res;
}

vector<Point> convex_hull_Andrew(vector<Point> a) {
    if(a.size() <= 2) return {}; // 或 return a
    sort(a.begin(), a.end());
    vector<Point> res;
    for(int i = 0; i < a.size(); ++i) {
        while(res.size() > 1 && !turn_left(res[res.size() - 2], res[res.size() - 1], a[i])) {
            res.pop_back();
        }
        res.push_back(a[i]);
    }
    int fix = res.size();
    for(int i = a.size() - 2; i >= 0; --i) {
        while(res.size() > fix && !turn_left(res[res.size() - 2], res[res.size() - 1], a[i])) {
            res.pop_back();
        }
        res.push_back(a[i]);
    }
    res.pop_back();
    return res;
}

void solve () {
    int n;
    cin >> n;
    vector<Point> p(n);
    for(int i = 0; i < n; ++i) cin >> p[i];
    p.push_back(p[0]);
    p.push_back(p[1]);

    for(int i = 0; i < n; ++i) {
        int j = i + 1, k = i + 2;
        if(sgn(det(p[k] - p[j], p[i] - p[j])) < 0) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int Task = 1;
    // cin >> Task;
    while (Task--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3940kb

input:

4
0 0
0 1
1 1
1 0

output:

No

result:

wrong answer expected YES, found NO