QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#623014#7906. Almost Convexclouds_WA 3ms13008kbC++232.4kb2024-10-09 09:35:212024-10-09 09:35:23

Judging History

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

  • [2024-10-09 09:35:23]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13008kb
  • [2024-10-09 09:35:21]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define Vector Point
#define int long long
const double eps = 1e-8, pi = acos(-1);
const int N = 2e5 + 10;
struct Point
{
    Point(int X = 0, int Y = 0) { x = X, y = Y; }
    int x, y;
    int fg;
} p[N], s[N];
Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator*(Vector a, double b) { return Vector(a.x * b, a.y * b); }
bool operator==(Vector a, Vector b) { return a.x == b.x && a.y == b.y; }
int dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
int cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double Len(Vector a) { return sqrt(1.0 * dot(a, a)); }

Point O;
bool tbcmp(Point a, Point b)
{
    if (cross(O - a, O - b) == 0)
        return Len(O - a) < Len(O - b);
    return cross(a - O, b - O) > 0;
}
vector<Point> ans2;
vector<Point> gettb(Point *p, int n)
{
    for (int i = 1; i <= n; i++)
    {
        if (p[i].y < p[1].y || p[i].y == p[1].y && p[i].x < p[1].x)
            swap(p[1], p[i]);
    }
    O = p[1];
    sort(p + 2, p + n + 1, tbcmp);
    vector<Point> ans;
    ans.push_back(p[1]);
    int idx = 0;
    for (int i = 2; i <= n; i++)
    {
        while (idx >= 1 && cross(ans[idx] - ans[idx - 1], p[i] - ans[idx]) <= 0)
            idx--, ans2.push_back(ans.back()), ans.pop_back();
        idx++;
        ans.push_back(p[i]);
    }
    return ans;
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;
    vector<Point> ans1 = gettb(p, n);
    int ans = 1;
    for (auto i : ans2)
    {
        int num = 0;
        for (auto j : ans1)
            s[++num] = j, s[num].fg = 1;
        for (auto j : ans2)
        {
            if (j.x == i.x && j.y == i.y)
                continue;
            s[++num] = j;
            s[num].fg = 0;
        }
        O = i;
        sort(s + 1, s + num + 1, tbcmp);

        for (int j = 1; j <= num; j++)
        {
            Point p1 = s[j], p2 = s[j % num + 1];
            if (p1.fg == 1 && p2.fg == 1)
                ans++;
        }
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(1);
    int t = 1;
    while (t--)
        solve();
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 13008kb

input:

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

output:

10

result:

wrong answer 1st numbers differ - expected: '9', found: '10'