QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111020#6436. Paimon Polygon5abCompile Error//C++173.7kb2023-06-05 14:39:422023-06-05 14:39:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-05 14:39:43]
  • 评测
查看
  • [2023-06-05 14:39:42]
  • 提交

answer

/* name: 6436
 * author: 5ab
 * created at: 2023-06-04
 */
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
using db = double;

const int max_n = 500000;

struct point
{
	int x, y;
	point operator-(const point& rhs) const {
		return point{ x - rhs.x, y - rhs.y };
	}
	bool operator==(const point& rhs) const = default;
}
a[max_n], b[max_n + 1];

inline void chmax(db& _a, db _b) { if (_a < _b) _a = _b; }
inline bool cclkw(point x, point y)
{
	return 1ll * x.x * y.y > 1ll * x.y * y.x;
}
inline bool cln(point x, point y)
{
	return 1ll * x.x * y.y == 1ll * x.y * y.x;
}
inline db dis(point x, point y)
{
	return hypot(x.x - y.x, x.y - y.y);
}

template<class It>
void cr(It bg, It ed)
{
	swap(*bg, *max_element(bg, ed, [](auto& x, auto& y) {
		return x.x == y.x ? x.y < y.y : x.x < y.x;
	}));
	sort(bg + 1, ed, [&](auto& lhs, auto& rhs) {
		return cclkw(lhs - *bg, rhs - *bg);
	});
}

template<class It>
db calc(It bg, It ed)
{
	db res = dis(*bg, *prev(ed));
	for (auto s = bg, t = next(bg); t != ed; s++, t++)
		res += dis(*s, *t);
	return res;
}

db solve1(int n)
{
	b[0] = {0, 0};
	copy(a, a + n, b + 1);
	cr(b, b + n + 1);
	
	static vector<point> c1, c2;
	c1.clear(), c2.clear();
	
	for (int i = 0; i <= n; i++)
	{
		while (ssize(c1) > 1 && cclkw(b[i] - c1.back(), c1.back() - end(c1)[-2]))
			c2.push_back(c1.back()), c1.pop_back();
		c1.push_back(b[i]);
	}
	// for (auto [x, y] : c1)
	// 	cerr << "(" << x << "," << y << ") ";
	// cerr << endl;
	
	// check colinearity
	for (int i = 1; i < ssize(c1) - 1; i++)
		if (cln(c1[i + 1] - c1[i], c1[i] - c1[i - 1]))
			return 0;
	for (int i = 1; i <= n; i++)
		if (c1.back() != b[i] && cln(c1.back() - b[i], b[i] - b[0]))
			return 0;
	if (find(c1.begin(), c1.end(), point{0, 0}) == c1.end())
		return 0;
	
	c2.push_back(point{0, 0});
	cr(c2.begin(), c2.end());
	for (int i = 0; i < ssize(c2); i++)
		if (!cclkw(c2[i] - c2[(i - 1 + ssize(c2)) % ssize(c2)], c2[(i + 1) % ssize(c2)] - c2[i]))
			return 0;
	
	return calc(c1.begin(), c1.end()) + calc(c2.begin(), c2.end());
}

db solve2(int n)
{
	int l = partition(a, a + n, [](auto& x) {
		return x.y < 0 || (x.y == 0 && x.x > 0);
	}) - a;
	sort(a, a + l, cclkw), sort(a + l, a + n, cclkw);
	
	auto nxt = [&](int x) {
		return x + 1 == n ? 0 : x + 1;
	};
	for (int i = 0; i < n; i++)
		if (cln(a[i], a[nxt(i)]))
			return 0;
	
	db ans = 0, bsv = calc(a, a + n);
	vector<int> xps;
	
	auto pre = [&](int x) {
		return x == 0 ? n - 1 : x - 1;
	};
	for (int i = 0; i < n; i++)
		if (!cclkw(a[i] - a[pre(i)], a[nxt(i)] - a[i]))
			xps.push_back(i);
	if (xps.size() > 4)
		return 0;
	
	auto od = [&](int id) {
		return hypot(a[id].x, a[id].y);
	};
	for (int i = 0, j = 1; i < n; i++)
	{
		while (nxt(j) != i && !cclkw(point{0, 0} - a[i], a[nxt(j)]))
		{
			// cerr << i << " " << j << " " << a[i].x << " " << a[i].y << " " << a[nxt(j)].x << " " << a[nxt(j)].y << endl;
			j = nxt(j);
		}
		if (!cclkw(point{0, 0} - a[j], a[nxt(i)]))
			continue;
		bool ok = true;
		for (int x : xps)
			if (x != i && x != j && x != nxt(i) && x != nxt(j))
			{
				ok = false;
				break;
			}
		if (ok)
			chmax(ans, bsv - dis(a[i], a[nxt(i)]) - dis(a[j], a[nxt(j)])
			               + od(i) + od(nxt(i)) + od(j) + od(nxt(j)));
	}
	return ans;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int cas, n;
	
	cin >> cas;
	while (cas--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> a[i].x >> a[i].y;
		
		cout << fixed << setprecision(10) << max(solve1(n), solve2(n)) << "\n";
	}
	
	return 0;
}
// started coding at: 06-04 17:50:44
源文件, 语言: C++17

详细 

answer.code:23:14: error: defaulted ‘bool point::operator==(const point&) const’ only available with ‘-std=c++20’ or ‘-std=gnu++20’
   23 |         bool operator==(const point& rhs) const = default;
      |              ^~~~~~~~
answer.code: In function ‘db solve1(int)’:
answer.code:72:24: error: ‘ssize’ was not declared in this scope; did you mean ‘ssize_t’?
   72 |                 while (ssize(c1) > 1 && cclkw(b[i] - c1.back(), c1.back() - end(c1)[-2]))
      |                        ^~~~~
      |                        ssize_t
answer.code:81:29: error: ‘ssize’ was not declared in this scope; did you mean ‘ssize_t’?
   81 |         for (int i = 1; i < ssize(c1) - 1; i++)
      |                             ^~~~~
      |                             ssize_t
answer.code:85:31: error: no match for ‘operator!=’ (operand types are ‘__gnu_cxx::__alloc_traits<std::allocator<point>, point>::value_type’ {aka ‘point’} and ‘point’)
   85 |                 if (c1.back() != b[i] && cln(c1.back() - b[i], b[i] - b[0]))
      |                     ~~~~~~~~~ ^~ ~~~~
      |                            |        |
      |                            |        point
      |                            __gnu_cxx::__alloc_traits<std::allocator<point>, point>::value_type {aka point}
In file included from /usr/include/c++/11/iosfwd:40,
                 from /usr/include/c++/11/ios:38,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from answer.code:5:
/usr/include/c++/11/bits/postypes.h:227:5: note: candidate: ‘template<class _StateT> bool std::operator!=(const std::fpos<_StateT>&, const std::fpos<_StateT>&)’
  227 |     operator!=(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/11/bits/postypes.h:227:5: note:   template argument deduction/substitution failed:
answer.code:85:37: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<point>, point>::value_type’ {aka ‘point’} is not derived from ‘const std::fpos<_StateT>’
   85 |                 if (c1.back() != b[i] && cln(c1.back() - b[i], b[i] - b[0]))
      |                                     ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from answer.code:5:
/usr/include/c++/11/bits/stl_pair.h:496:5: note: candidate: ‘template<class _T1, class _T2> constexpr bool std::operator!=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)’
  496 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:496:5: note:   template argument deduction/substitution failed:
answer.code:85:37: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<point>, point>::value_type’ {aka ‘point’} is not derived from ‘const std::pair<_T1, _T2>’
   85 |                 if (c1.back() != b[i] && cln(c1.back() - b[i], b[i] - b[0]))
      |                                     ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from answer.code:5:
/usr/include/c++/11/bits/stl_iterator.h:428:5: note: candidate: ‘template<class _Iterator> constexpr bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)’
  428 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:428:5: note:   template argument deduction/substitution failed:
answer.code:85:37: note:   ‘__gnu_cxx::__alloc_traits<std::allocator<point>, point>::value_type’ {aka ‘point’} is not derived from ‘const std::reverse_iterator<_Iterator>’
   85 |                 if (c1.back() != b[i] && cln(c1.back() - b[i], b[i] - b[0]))
      |                                     ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from answer.code:5:
/usr/include/c++/11/bits/stl_iterator.h:467:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)’
  467 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:467:5: note:   template argument deduction/substitution failed:
answer.code:85:37: note:   ‘__gnu_cxx::__alloc_traits<std::alloc...
English 繁體中文 简体中文

服务器时间: 2024-12-02 21:48:30 | 开源项目