QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313664#7730. Convex CheckerwritingdogCompile Error//C++202.9kb2024-01-24 22:00:562024-01-24 22:00:56

Judging History

This is the latest submission verdict.

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-01-24 22:00:56]
  • Judged
  • [2024-01-24 22:00:56]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
typedef unsigned long long ull;

const int N = 1e5;
const int INF = 0x3f3f3f3f3f3f3f3f;

typedef int LD;
const double eps = 1e-8; // 控制精度

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

LD sqr(LD x)
{
    return x * x;
}

struct point
{
    LD x, y;
    point operator-(const point &a) const
    {
        return {x - a.x, y - a.y};
    }
    friend bool operator==(const point &a, const point &b) // 点相等
    {
        return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
    }
};
LD dis(const point &a, const point &b)
{
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

LD det(const point &a, const point &b)
{
    return a.x * a.y + b.x * b.y;
}

bool turn_left(const point &a, const point &b, const point &c)
{
    return sgn(det(b - a, c - a)) > 0; // 叉积为正
}
vector<point> convex_hull(vector<point> a)
{
    if (a.size() <= 2)
        return a;                                  // 或者 return {};
    point base = *min_element(a.begin(), a.end()); // 字典序: less <pair >
    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> ret;
    for (auto i : a)
    {
        while (ret.size() > 1 && !turn_left(a[ret.size() - 2], a[ret.size() - 1], i))
        {
            ret.pop_back();
        }
        ret.push_back(i);
    }
    return ret;
}
bool cmp(point base, point u, point v)
{
    int s = sgn(det(u - base, v - base));
    if (s)
        return s > 0;
    else
        return sgn(dis(u, base) - dis(v, base)) < 0;
}

void solve()
{
    int n;
    cin >> n;
    vector<point> a(n);
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    if (!turn_left(a[1], a[2], a[3]))
        reverse(a.begin(), a.end());

    point base = *min_element(a.begin(), a.end());
    int idx = 0;
    while (!(a[idx] == base))
        idx++;
    for (int t = 1; t <= n-2; ++t)
    {   
        int i = (idx + t) % n, j = (idx+t+1) % n;
        if(!cmp(a[idx],a[i],a[j]))
        {
            cout << "No\n";
            return;
        }
    }

    for (int t = 1; t <= n; ++t)
    {   
        int i = (idx + 1) % n, j = (idx + 2) % n;
        if (!turn_left(a[idx], a[i], a[j]))
        {
            cout << "No" << endl;
            return;
        }
        idx = i;
    }
    cout << "Yes" << endl;
}

signed main()
{
    // cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        solve();
    }
    return 0;
}
/*

*/

Details

In file included from /usr/include/c++/13/bits/stl_algobase.h:71,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<point*, std::vector<point> >; _Iterator2 = __gnu_cxx::__normal_iterator<point*, std::vector<point> >]’:
/usr/include/c++/13/bits/stl_algo.h:5651:12:   required from ‘constexpr _ForwardIterator std::__min_element(_ForwardIterator, _ForwardIterator, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<point*, vector<point> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/13/bits/stl_algo.h:5675:43:   required from ‘constexpr _FIter std::min_element(_FIter, _FIter) [with _FIter = __gnu_cxx::__normal_iterator<point*, vector<point> >]’
answer.code:54:30:   required from here
/usr/include/c++/13/bits/predefined_ops.h:45:23: error: no match for ‘operator<’ (operand types are ‘point’ and ‘point’)
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:67:
/usr/include/c++/13/bits/stl_iterator.h:1189:5: note: candidate: ‘template<class _IteratorL, class _IteratorR, class _Container> constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL> __gnu_cxx::operator<=>(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)’ (reversed)
 1189 |     operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1189:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/predefined_ops.h:45:23: note:   ‘point’ is not derived from ‘const __gnu_cxx::__normal_iterator<_IteratorL, _Container>’
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1208:5: note: candidate: ‘template<class _Iterator, class _Container> constexpr std::__detail::__synth3way_t<_T1> __gnu_cxx::operator<=>(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)’ (rewritten)
 1208 |     operator<=>(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1208:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/predefined_ops.h:45:23: note:   ‘point’ is not derived from ‘const __gnu_cxx::__normal_iterator<_Iterator, _Container>’
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~