QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#537853#7730. Convex Checker0x3eaWA 0ms3876kbC++173.1kb2024-08-30 19:06:332024-08-30 19:06:33

Judging History

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

  • [2024-08-30 19:06:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2024-08-30 19:06:33]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define Vector Point
using namespace std;
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 5e3 + 10;
const int mod = 998244353;
ll sign(ll a) { return a < 0 ? -1 : a > 0; }
struct Point
{
    db x, y;
    Point() {}
    Point(db x, db y) : x(x), y(y) {}
    Point operator+(Point p) { return {x + p.x, y + p.y}; }
    Point operator-(Point p) { return {x - p.x, y - p.y}; }
    Point operator*(db d) { return {x * d, y * d}; }
    Point operator/(db d) { return {x / d, y / d}; }
    bool operator==(Point &p) const { return !sign(x - p.x) && !sign(y - p.y); }
    int toleft(Point b)
    { // 点在线段的方向
        ll res = x * b.y - y * b.x;
        if (res == 0)
            return 0; // 直线上
        else if (res > 0)
            return 1; // 左
        return -1;    // 右
    }
    friend istream &operator>>(istream &is, Point &p)
    {
        return is >> p.x >> p.y;
    }
    friend ostream &operator<<(ostream &os, Point p)
    {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};
bool operator<(const Point &p1, const Point &p2)
{
    if (p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}
db dot(Point a, Point b)
{
    return a.x * b.x + a.y * b.y;
}
db cross(Point a, Point b)
{
    return a.x * b.y - a.y * b.x;
}
db dis1(Point a, Point b)
{ // 两点距离的平方
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    // return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));//long double ver
}
db dis2(Point a, Point b)
{ // 两点距离的平方
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool ver(Vector a, Vector b)
{ // 是否垂直
    return sign(dot(a, b)) == 0;
}
vector<Point> Andrew(vector<Point> &s)
{
    sort(s.begin(), s.end());
    int tp = 0;
    vector<int> stk(s.size() + 10, 0);
    stk[++tp] = 0;
    vector<bool> used(s.size() + 1, 0);
    for (int i = 1; i < s.size(); i++)
    {
        while (tp >= 2 && cross(s[stk[tp]] - s[stk[tp - 1]], s[i] - s[stk[tp]]) <= 0)
            used[stk[tp--]] = 0;
        used[i] = 1;
        stk[++tp] = i;
    }
    int sz = tp;
    for (int i = (int)s.size() - 2; i >= 0; i--)
    {
        if (used[i])
            continue;
        while (tp > sz && cross(s[stk[tp]] - s[stk[tp - 1]], s[i] - s[stk[tp]]) <= 0)
            used[stk[tp--]] = 0;
        used[i] = 1;
        stk[++tp] = i;
    }
    vector<Point> ans;
    for (int i = 1; i < tp; i++)
        ans.push_back(s[stk[i]]);
    return ans;
}
void solve()
{
    int n;
    cin >> n;
    vector<Point> a(n);
    for (auto &i : a)
        cin >> i;

    auto res = Andrew(a);
    for (auto i : res)
        cout << i << endl;
    cout << (res.size() == n ? "Yes" : "No") << endl;
}
int main()
{
#ifdef x3ea
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // cin >> _;
    for (; _; _--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3876kb

input:

3
0 0
1 0
0 1

output:

(0, 0)
(1, 0)
(0, 1)
Yes

result:

wrong output format YES or NO expected, but (0, found