QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729273 | #9520. Concave Hull | am_i | Compile Error | / | / | C++20 | 5.6kb | 2024-11-09 16:48:56 | 2024-11-09 16:48:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define V vector<int>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
const int N=2e5+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,k,a,b;
typedef __int128 rr;
typedef pair<__int128,__int128> rrr;
//const double eps = 1e-10;
struct Point {
__int128 x, y;
bool operator<(const Point& p) const {
return x < p.x || (x == p.x && y < p.y);
}
};
struct Vector {
__int128 x,y;
Vector(__int128 x = 0, __int128 y = 0) : x(x), y(y) {}
Vector operator+(const Vector& v) const {
return Vector(x + v.x, y + v.y);
}
Vector operator-(const Vector& v) const {
return Vector(x - v.x, y - v.y);
}
};
__int128 aabs(__int128 a){
if(a < 0) return (-1*a);
else return a;
}
__int128 TriangleArea(Point a,Point b,Point c){
Vector A1(a.x-b.x,a.y-b.y),A2(a.x-c.x,a.y-c.y);
//S = |x1y2-x2y1| / 2 <==>(1/2 * |A1 x A2|)
__int128 S = (A1.x*A2.y-A2.x*A1.y);
return S;
}
// 叉积判断点p是否在向量ab的左边,右边,或在直线上
__int128 cross(const Point& a, const Point& b, const Point& p) {
return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
}
// Graham Scan 算法求凸包
vector<Point> convexHull(vector<Point>& points) {
int n = points.size();
sort(points.begin(), points.end());
//points.erase(unique(points.begin(),points.end()),points.end());
vector<Point> hull;
// 构建凸包下半部分
for (int i = 0; i < n; ++i) {
while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
// 构建凸包上半部分
for (int i = n - 1, t = hull.size() + 1; i >= 0; --i) {
while (hull.size() >= t && cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
hull.pop_back(); // 去掉重复的最后一个点
return hull;
}
void solve(){
cin>>n;
vector<Point> a(n+1),tmp;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
a[i]={x,y};
}
vector<Point> ou,in;
ou = convexHull(a);
set<rrr> st;
for(int i=0;i<ou.size();i++){
st.insert(ou[i]);
}
for(auto [aa,bb]:a){
if(!st.count({aa,bb}))tmp.push_back({aa,bb});
}
__int128 ans=0;
for(int j=2;j<ou.size();j++){
ans+=TriangleArea(ou[0],ou[j-1],ou[j]);
}
in = convexHull(tmp);
if(tmp.size()<=2){
__int128 t=1000000000000000000000;
ou.push_back(ou[0]);
for(int k=0;k<tmp.size();k++){
for(int j=1;j<ou.size();j++){
t=min(t,TriangleArea(tmp[k],ou[j-1],ou[j]));
}
}
// if(ans-t==1184240922443768439)cout<<"1\n";
if(ans-t>0)
cout<<(int)(ans-t)<<"\n";
else cout<<"-1\n";
}
else if(in.size()<=2){
__int128 t=1000000000000000000000;
ou.push_back(ou[0]);
for(int k=0;k<in.size();k++){
for(int j=1;j<ou.size();j++){
t=min(t,TriangleArea(in[k],ou[j-1],ou[j]));
}
}
// if(ans-t==1184240922443768439)cout<<"2\n";
if(ans-t>0)
cout<<(int)(ans-t)<<"\n";
else cout<<"-1\n";
}
else {
__int128 t=1000000000000000000000;
int d=0;
__int128 mx=1000000000000000000000,p=0;
for(int i=0;i<in.size();i++){
int tt=TriangleArea(ou[0],ou[1],in[i]);
if(tt<mx)mx=tt,p=i;
}
d=p;
ou.push_back(ou[0]);
for(int j=1;j<ou.size();j++){
__int128 la=TriangleArea(in[d],ou[j-1],ou[j]);
while(1){
t=min(t,la);
if(d+1<in.size()&&TriangleArea(in[d+1],ou[j-1],ou[j])<=la){
la=TriangleArea(in[d+1],ou[j-1],ou[j]);
d++;
}
else if(d+1>=in.size()&&TriangleArea(in[(d+1)%in.size()],ou[j-1],ou[j])<=la){
la=TriangleArea(in[(d+1)%in.size()],ou[j-1],ou[j]);
d=(d+1)%in.size();
}
// else if(d-1>=0&&TriangleArea(in[d-1],ou[j-1],ou[j])<la){
// la=TriangleArea(in[d-1],ou[j-1],ou[j]);
// d--;
// }
// else if(d==0&&TriangleArea(in[in.size()-1],ou[j-1],ou[j])<la){
// la=TriangleArea(in[in.size()-1],ou[j-1],ou[j]);
// d=in.size()-1;
// }
else break;
}
// for(int r=0;r<tmp.size();r++){
// // t=min(t,TriangleArea(in[r],ou[j-1],ou[j]));
// __int128 tt=TriangleArea(tmp[p],ou[j-1],ou[j]);
// p=(p+1)%tmp.size();
// if(tt>=0)t=min(t,tt);
// else break;
// }
}
// if(ans-t==1184240922443768439){
// //cout<<t<<"\n";
// cout<<(int)ans<<"000"<<(int)t<<"\n";
// }
if(ans-t>0)
cout<<(int)(ans-t)<<"\n";
else cout<<"-1\n";
}
}
signed main(){
cin.tie(0)->ios::sync_with_stdio(0);
cout.tie(0);
//cout<<fixed<<setprecision(12);
int t=1;
cin>>t;
while(t--){
solve();
}
}
//1164835025329039520
//1184240922443768439
//384454336
//1184240922828222775
//1184240921819167448
//19405896490127928
详细
answer.code:104:20: warning: integer constant is too large for its type 104 | __int128 t=1000000000000000000000; | ^~~~~~~~~~~~~~~~~~~~~~ answer.code:117:20: warning: integer constant is too large for its type 117 | __int128 t=1000000000000000000000; | ^~~~~~~~~~~~~~~~~~~~~~ answer.code:130:20: warning: integer constant is too large for its type 130 | __int128 t=1000000000000000000000; | ^~~~~~~~~~~~~~~~~~~~~~ answer.code:132:21: warning: integer constant is too large for its type 132 | __int128 mx=1000000000000000000000,p=0; | ^~~~~~~~~~~~~~~~~~~~~~ answer.code: In function ‘void solve()’: answer.code:93:18: error: no matching function for call to ‘std::set<std::pair<__int128, __int128> >::insert(__gnu_cxx::__alloc_traits<std::allocator<Point>, Point>::value_type&)’ 93 | st.insert(ou[i]); | ~~~~~~~~~^~~~~~~ In file included from /usr/include/c++/13/set:63, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:158, from answer.code:1: /usr/include/c++/13/bits/stl_set.h:568:9: note: candidate: ‘template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _Key = std::pair<__int128, __int128>; _Compare = std::less<std::pair<__int128, __int128> >; _Alloc = std::allocator<std::pair<__int128, __int128> >]’ 568 | insert(_InputIterator __first, _InputIterator __last) | ^~~~~~ /usr/include/c++/13/bits/stl_set.h:568:9: note: template argument deduction/substitution failed: answer.code:93:18: note: candidate expects 2 arguments, 1 provided 93 | st.insert(ou[i]); | ~~~~~~~~~^~~~~~~ /usr/include/c++/13/bits/stl_set.h:511:7: note: candidate: ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<__int128, __int128>; _Compare = std::less<std::pair<__int128, __int128> >; _Alloc = std::allocator<std::pair<__int128, __int128> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<__int128, __int128>, std::pair<__int128, __int128>, std::_Identity<std::pair<__int128, __int128> >, std::less<std::pair<__int128, __int128> >, std::allocator<std::pair<__int128, __int128> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<__int128, __int128> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<__int128, __int128> >, std::pair<__int128, __int128> >::rebind<std::pair<__int128, __int128> >; typename _Alloc::value_type = std::pair<__int128, __int128>; value_type = std::pair<__int128, __int128>]’ 511 | insert(const value_type& __x) | ^~~~~~ /usr/include/c++/13/bits/stl_set.h:511:32: note: no known conversion for argument 1 from ‘__gnu_cxx::__alloc_traits<std::allocator<Point>, Point>::value_type’ {aka ‘Point’} to ‘const std::set<std::pair<__int128, __int128> >::value_type&’ {aka ‘const std::pair<__int128, __int128>&’} 511 | insert(const value_type& __x) | ~~~~~~~~~~~~~~~~~~^~~ /usr/include/c++/13/bits/stl_set.h:520:7: note: candidate: ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(value_type&&) [with _Key = std::pair<__int128, __int128>; _Compare = std::less<std::pair<__int128, __int128> >; _Alloc = std::allocator<std::pair<__int128, __int128> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<__int128, __int128>, std::pair<__int128, __int128>, std::_Identity<std::pair<__int128, __int128> >, std::less<std::pair<__int128, __int128> >, std::allocator<std::pair<__int128, __int128> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<__int128, __int128> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<__int128, __int128> >, std::pair<__int128, __int128> >::rebind<std::pair<__int128, __int128> >; typename _Alloc::value_type = std::pair<__int128, __int128>; value_type = std::pair<__int128, __int128>]’ 520 | insert(value_type&& __x) | ^~~~~~ /usr/include/c++/13/bits/stl_set.h:520:27: note: no known conversion for argument 1 from ‘__gnu_cxx::__alloc_traits<std::allocator<Point>, Point>::value_type’ {aka ‘Point’} to ‘std::set<std::pair<__int128, __...