QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#736472#9520. Concave HullxsdgpCompile Error//C++202.4kb2024-11-12 11:16:252024-11-12 11:16:26

Judging History

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

  • [2024-11-12 11:16:26]
  • 评测
  • [2024-11-12 11:16:25]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,m;
struct VECTOR
{
	int x,y;
	int operator^(const VECTOR &v)const
	{
		return x*v.y-y*v.x;
	}
};
struct POINT
{
	int x,y;
	bool operator<(const POINT &p)const
	{
		if(x==p.x)return y<p.y;
		else return x<p.x;
	VECTOR operator-(const POINT &p)const
	{
		return {x-p.x,y-p.y};
	}
}p[100005],p1[100005];
int cross(VECTOR v1,VECTOR v2)
{
	return v1^v2;
}
vector<POINT> st,st1;
bool check(POINT p)
{
	POINT back1=st.back(),back2=*(st.rbegin()+1);
	return cross(back1-back2,p-back1)<=0;
}
void andrew()
{
	st.clear();
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)
	{
		while(st.size()>1&&check(p[i]))st.pop_back();
		st.push_back(p[i]);
	}
	int k=st.size();
	for(int i=n-1;i>=1;i--)
	{
		while(st.size()>k&&check(p[i]))st.pop_back();
		st.push_back(p[i]);
	}
	st.pop_back();
}
bool check1(POINT p)
{
	POINT back1=st1.back(),back2=*(st1.rbegin()+1);
	return cross(back1-back2,p-back1)<=0;
}
void andrew1()
{
	st1.clear();
	sort(p1+1,p1+m+1);
	for(int i=1;i<=m;i++)
	{
		while(st1.size()>1&&check1(p1[i]))st1.pop_back();
		st1.push_back(p1[i]);
	}
	int k=st1.size();
	for(int i=m-1;i>=1;i--)
	{
		while(st1.size()>k&&check1(p1[i]))st1.pop_back();
		st1.push_back(p1[i]);
	}
	st1.pop_back();
}
int rotcaliper()
{
	int j=0,sub=1e18;
	VECTOR v=st[1]-st[0];
	while(m!=1&&cross(v,st1[(j+1)%st1.size()]-st[0])<=cross(v,st1[j]-st[0]))j=(j+1)%st1.size();
	while(m!=1&&cross(v,st1[(j-1+st1.size())%st1.size()]-st[0])<=cross(v,st1[j]-st[0]))j=(j-1+st1.size())%st1.size();
	for(int i=0;i<st.size();i++)
	{
		int i1=(i+1)%st.size();
		VECTOR v=st[i1]-st[i];
		while(m!=1&&cross(v,st1[(j+1)%st1.size()]-st[i])<=cross(v,st1[j]-st[i]))j=(j+1)%st1.size();
		sub=min(sub,cross(v,st1[j]-st[i]));
	}
	return sub;
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i].x>>p[i].y;
	andrew();
	int sum=0;
	for(int i=0;i<st.size();i++)
	{
		mp[st[i]]=1;
		POINT o={0,0};
		sum+=cross(st[i]-o,st[(i+1)%st.size()]-o);
	}
	m=0;
	for(int i=1;i<=n;i++)
		if(mp.find(p[i])==mp.end())p1[++m]=p[i];
	
	
	if(m==0)cout<<-1<<endl;
	else
	{
		andrew1();
		cout<<sum-rotcaliper()<<endl;
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}
/*
3
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1
5
-2 0
1 -2
5 2
0 4
3 1
*/

詳細信息

answer.code:25:2: error: ‘p’ does not name a type
   25 | }p[100005],p1[100005];
      |  ^
answer.code:122:2: error: expected ‘}’ at end of input
  122 | }
      |  ^
answer.code:15:1: note: to match this ‘{’
   15 | {
      | ^
answer.code: In member function ‘bool POINT::operator<(const POINT&) const’:
answer.code:22:9: error: a function-definition is not allowed here before ‘{’ token
   22 |         {
      |         ^
answer.code: In member function ‘bool POINT::check(POINT)’:
answer.code:34:27: error: no match for ‘operator-’ (operand types are ‘POINT’ and ‘POINT’)
   34 |         return cross(back1-back2,p-back1)<=0;
      |                      ~~~~~^~~~~~
      |                      |     |
      |                      POINT POINT
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,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_iterator.h:625:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)’
  625 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:625:5: note:   template argument deduction/substitution failed:
answer.code:34:28: note:   ‘POINT’ is not derived from ‘const std::reverse_iterator<_IteratorL>’
   34 |         return cross(back1-back2,p-back1)<=0;
      |                            ^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’
 1800 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note:   template argument deduction/substitution failed:
answer.code:34:28: note:   ‘POINT’ is not derived from ‘const std::move_iterator<_IteratorL>’
   34 |         return cross(back1-back2,p-back1)<=0;
      |                            ^~~~~
In file included from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/complex:365:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&, const complex<_Tp>&)’
  365 |     operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:365:5: note:   template argument deduction/substitution failed:
answer.code:34:28: note:   ‘POINT’ is not derived from ‘const std::complex<_Tp>’
   34 |         return cross(back1-back2,p-back1)<=0;
      |                            ^~~~~
/usr/include/c++/13/complex:374:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&, const _Tp&)’
  374 |     operator-(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:374:5: note:   template argument deduction/substitution failed:
answer.code:34:28: note:   ‘POINT’ is not derived from ‘const std::complex<_Tp>’
   34 |         return cross(back1-back2,p-back1)<=0;
      |                            ^~~~~
/usr/include/c++/13/complex:383:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const _Tp&, const complex<_Tp>&)’
  383 |     operator-(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:383:5: note:   template argument deduction/substitution failed:
answer.code:34:28: note:   ‘POINT’ is not derived from ‘const std::complex<_Tp>’
   34 |         return cross(back1-back2,p-back1)<=0;
      |                            ^~~~~
/usr/include/c++/13/complex:460:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&)’
  460 |     operator-(const complex<_Tp>& __x)
      |     ^~~~~~~~
/usr/include/c++/13/complex:460:5: note:   template argument deduction/substitution failed:
answer.code:34:28: note:   ‘POINT’ is not derived from ‘const std::complex<_Tp>’
   34 |         return cross(back1-back2,p-back1)<=0;
      |                            ^~~~~
In file included from /usr/include/c++/13/valarray:605,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: ‘template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)’
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/1...