QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#573485#7906. Almost Convexrxzfn639Compile Error//C++233.8kb2024-09-18 18:58:452024-09-18 18:58:53

Judging History

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

  • [2024-09-18 18:58:53]
  • 评测
  • [2024-09-18 18:58:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define il inline
const int N = 3e3 + 5;


const double eps = 1e-8;
il int sgn(double x)
{
    // 进行判断, 提高精度
    if (fabs(x) <= eps)
        return 0;          // x == 0, 精度范围内的近似相等
    return x > 0 ? 1 : -1; // 返回正负
}
il bool eq(double a, double b) { return abs(a - b) < eps; } // ==
il bool le(double a, double b) { return a - b < eps; }      // <=
il bool lt(double a, double b) { return a - b < -eps; }     // <
typedef struct Point
{
    int x, y;
    // Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数, 初始值为 0

    // 重载运算符
    // 点 - 点 = 向量 (向量AB = B - A)
    Point operator-(const Point &B) const { return Point(x - B.x, y - B.y); }

    // 点 + 点 = 点, 点 + 向量 = 向量, 向量 + 向量 = 向量
    Point operator+(const Point &B) const { return Point(x + B.x, y + B.y); }

    // 向量 · 向量 (点积)
    double operator*(const Point &B) const { return x * B.x + y * B.y; }

    // 向量 × 向量 (叉积)
    double operator^(const Point &B) const { return x * B.y - y * B.x; }

    // 判断大小, 一般用于排序
    bool operator<(const Point &B) const { return x < B.x || (x == B.x && y < B.y); }

} Vector;

using Points = vector<Point>;

// 极角排序
// Need: (^, sgn)
// 基准点
Point p0;
il double theta(auto p) { return atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = p0)              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p1 - c), theta(p2 - c));
    });
}

// 凸包
// Andrew算法求凸包,最后一个点与第一个点重合
// Need: (^,-,<), sgn, le
il bool check(Point p, Point q, Point r) { return le(0, (q - p) ^ (r - q)); }
vector<Point> Andrew(Points poly)
{
    int n = poly.size(), top = 0;
    vector<int> stk(n + 10, 0), used(n + 10, 0);
    sort(poly.begin(), poly.end());
    stk[++top] = 0;
    for (int i = 1; i < n; i++)
    {
        while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
            used[stk[top--]] = 0;

        used[i] = 1;
        stk[++top] = i;
    }
    int tmp = top;
    for (int i = n - 2; i >= 0; i--)
    {
        if (used[i]) continue;
        while (top > tmp && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
            used[stk[top--]] = 0;

        used[i] = 1;
        stk[++top] = i;
    }
    vector<Point> a;
    for (int i = 1; i <= top; i++) a.push_back(poly[stk[i]]);
    return a;
}

const int mod = 1e9 + 7;
int hs(int x, int y)
{
    return (x * 100000000 + y) % mod;
}
Point temp[N];
void solve()
{
    int n;
    cin >> n;
    Points ans, p;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        p.push_back({a, b});
    }
    ans = Andrew(p);

    unordered_map<int, int> mp;
    for (auto [x, y]: ans) mp[hs(x, y)] = 1;
    
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        auto [x, y] = p[i];
        if (mp[hs(x, y)]) continue;

        p0 = p[i];
        int tn = 0;
        for (int j = 0; j < n; j++) 
        {
            if (j != i) temp[tn++] = p[j];
        }
        sort(temp, temp + tn, [&](auto p1, auto p2) {
            return lt(theta(p1 - p0), theta(p2 - p0));
        });

        for (int j = 0; j < tn; j++)
        {
            auto p1 = temp[j], p2 = temp[(j + 1) % tn];
            if(mp[hs(p1.x, p1.y)] && mp[hs(p2.x, p2.y)]) res++;
        }
    }
    cout << res + 1 << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; 
    while (T--) solve();
    return 0;
}

Details

answer.code: In function ‘std::vector<Point> Andrew(Points)’:
answer.code:69:94: error: no match for ‘operator<=’ (operand types are ‘Point’ and ‘int’)
   69 |         while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
      |                                                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~ ^~ ~
      |                                                                            |                    |
      |                                                                            Point                int
In file included from /usr/include/c++/13/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:181,
                 from answer.code:1:
/usr/include/c++/13/bits/regex.h:1288:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Alloc> auto std::__cxx11::operator<=>(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’ (reversed)
 1288 |     operator<=>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1288:5: note:   template argument deduction/substitution failed:
answer.code:69:97: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
   69 |         while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
      |                                                                                                 ^
/usr/include/c++/13/bits/regex.h:1456:5: note: candidate: ‘template<class _Bi_iter> auto std::__cxx11::operator<=>(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’ (reversed)
 1456 |     operator<=>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1456:5: note:   template argument deduction/substitution failed:
answer.code:69:97: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
   69 |         while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
      |                                                                                                 ^
/usr/include/c++/13/bits/regex.h:1629:5: note: candidate: ‘template<class _Bi_iter> auto std::__cxx11::operator<=>(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)’ (reversed)
 1629 |     operator<=>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1629:5: note:   template argument deduction/substitution failed:
answer.code:69:97: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
   69 |         while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
      |                                                                                                 ^
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/stl_iterator.h:583:5: note: candidate: ‘template<class _IteratorL, class _IteratorR>  requires  three_way_comparable_with<_IteratorR, _IteratorL, std::partial_ordering> constexpr std::compare_three_way_result_t<_IteratorL, _IteratorR> std::operator<=>(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)’ (reversed)
  583 |     operator<=>(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:583:5: note:   template argument deduction/substitution failed:
answer.code:69:97: note:   mismatched types ‘const std::reverse_iterator<_IteratorL>’ and ‘int’
   69 |         while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
      |                                                                                                 ^
/usr/include/c++/13/bits/stl_iterator.h:1690:5: note: candidate: ‘template<class _IteratorL, class _IteratorR>  requires  three_way_comparable_with<_IteratorR, _IteratorL, std::partial_ordering> constexpr std::compare_three_way_result_t<_IteratorL, _IteratorR> std::operator<=>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’ (reversed)
 1690 |     operator<=>(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1690:5: note:   template argument deduction/substitution failed:
answer.code:69:97: note:   mismatched types ‘const std::move_iterator<_IteratorL>’ and ‘int’
   69 |         while (top > 1 && (poly[stk[top]] - poly[stk[top - 1]]) ^ (poly[i] - poly[stk[top]]) <= 0)
      |                                                                                                 ^
In file included from /usr/include/c++/13/bits/ranges_algo.h:36,
                 from /usr/include/c++/13/algorithm:63:
/usr/include/c++/13/optional:1273:5: note: candidate: ‘template<class _Tp, class _Up>  requires  three_...