QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#658466#7906. Almost ConvexLeoGCompile Error//C++232.5kb2024-10-19 16:52:072024-10-19 16:52:09

Judging History

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

  • [2024-10-19 16:52:09]
  • 评测
  • [2024-10-19 16:52:07]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
int n, p, ans;
struct Point {
    int x, y;
    bool inside = true;
    Point(int xx = 0, int yy = 0) : x(xx), y(yy) {}
    bool operator==(const Point &b) const {
        return x == b.x && y == b.y;
    }
} lis[N], stk[N];
int cross(Point p0, Point p1, Point p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
bool cmp(Point a, Point b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
 
int dis(Point a, Point b) {
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}
double cos(Point a, Point b, Point c) {
    return (dis(a, b) + dis(b, c) - dis(a, c)) / (2 * sqrt(dis(a, b)) * sqrt(dis(b, c)));
}

void andrew() {
    p = 1;
    stk[0] = lis[0], stk[1] = lis[1];
    for (int i = 2; i < n; ++i) {
        while (p > 0 && cross(stk[p - 1], stk[p], lis[i]) <= 0) --p;
        stk[++p] = lis[i];
    }
    stk[++p] = lis[n - 2];
    for (int i = n - 3; i >= 0; --i) {
        while (p > 0 && cross(stk[p - 1], stk[p], lis[i]) <= 0) --p;
        stk[++p] = lis[i];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> lis[i].x >> lis[i].y;
    sort(lis, lis + n, cmp);
    andrew();
    vector<Point> ins;
    map<Point, vector<pair<double, double>>> angle;
    for (int i = 0; i < n; ++i) {   // for each point
        for (int j = 0; j < p; ++j) {   // for each edge
            if (lis[i] == stk[j]) {
                lis[i].inside = false;
                break;
            }
            if (angle.find(lis[i]) == angle.end()) {
                angle[lis[i]] = vector<pair<double, double>>(n);
            }
            angle[lis[i]][j] = {cos(lis[i], stk[j], stk[j + 1]), cos(lis[i], stk[j + 1], stk[j])};
        }
        if (lis[i].inside) ins.push_back(lis[i]);
    }
    for (int i = 0; i < p; ++i) {
        sort(ins.begin(), ins.end(), [&](Point a, Point b){
            return angle[a][i].first > angle[b][i].first;
        });
        double angle2 = 1;
        for (auto& po : ins) {
            if (po == ins[0]) {
                angle2 = angle[po][i].second;
                ans++;
            }
            else {
                if (angle[po][i].second > angle2) {
                    ans++;
                }
            }
        }
    }
    cout << ans + 1 << endl;
    return 0;
}

详细

In file included from /usr/include/c++/13/string:49,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_function.h: In instantiation of ‘constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Point]’:
/usr/include/c++/13/bits/stl_map.h:511:32:   required from ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = Point; _Tp = std::vector<std::pair<double, double> >; _Compare = std::less<Point>; _Alloc = std::allocator<std::pair<const Point, std::vector<std::pair<double, double> > > >; mapped_type = std::vector<std::pair<double, double> >; key_type = Point]’
answer.code:60:29:   required from here
/usr/include/c++/13/bits/stl_function.h:408:20: error: no match for ‘operator<’ (operand types are ‘const Point’ and ‘const Point’)
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/13/string:48:
/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:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   ‘const Point’ is not derived from ‘const std::reverse_iterator<_IteratorL>’
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/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:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   ‘const Point’ is not derived from ‘const std::move_iterator<_IteratorL>’
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:601:5: note: candidate: ‘template<class _Iterator>  requires  three_way_comparable<_Iterator, std::partial_ordering> constexpr std::compare_three_way_result_t<_Iterator, _Iterator> std::operator<=>(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorL>&)’ (rewritten)
  601 |     operator<=>(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:601:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   ‘const Point’ is not derived from ‘const std::reverse_iterator<_IteratorL>’
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1756:5: note: candidate: ‘template<class _Iterator>  requires  three_way_comparable<_Iterator, std::partial_ordering> constexpr std::compare_three_way_result_t<_Iterator, _Iterator> std::operator<=>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)’ (rewritten)
 1756 |     operator<=>(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1756:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   ‘const Point’ is not derived from ‘const std::move_iterator<_IteratorL>’
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:550:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&) requires requires{{std::operator<::__x->base() > std::operator<::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}’
  550 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:550:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   ‘const Point’ is not derived from ‘const std::reverse_iterator<_IteratorL>’
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1705:5: note: candi...