QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729273#9520. Concave Hullam_iCompile Error//C++205.6kb2024-11-09 16:48:562024-11-09 16:48:59

Judging History

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

  • [2024-11-09 16:48:59]
  • 评测
  • [2024-11-09 16:48:56]
  • 提交

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, __...