QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313664 | #7730. Convex Checker | writingdog | Compile Error | / | / | C++20 | 2.9kb | 2024-01-24 22:00:56 | 2024-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
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [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; } | ~~~~~~~^~~~~~~~