QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#729283#9520. Concave Hullam_iWA 32ms3820kbC++205.6kb2024-11-09 16:49:572024-11-09 16:49:57

Judging History

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

  • [2024-11-09 16:49:57]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:3820kb
  • [2024-11-09 16:49:57]
  • 提交

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].x,ou[i].y});
    }
    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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
-1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

2178418010787347715
1826413114144932145
1651687576234220014
1883871859778998985
2119126281997959892
894016174881844630
2271191316922158910
1998643358049669416
1740474221286618711
1168195646932543192

result:

ok 10 lines

Test #3:

score: -100
Wrong Answer
time: 32ms
memory: 3720kb

input:

1000
125
64661186 -13143076
302828013 -185438065
-418713797 -191594241
430218126 -397441626
354327250 -836704374
149668812 -598584998
311305970 66790541
199720625 -592356787
468137 -584752683
258775829 96211747
-358669612 -134890109
-129221188 -998432368
-277309896 -140056561
356901185 420557649
-51...

output:

1986320445246155278
1900093336073022078
1612088392301142476
2012259136539173407
1819942017252118749
1772230185841892196
1184240922443768439
1527446155241140517
1807368432185303666
1236918659444944569
1306839249967484778
1984123720246784099
1868728080720036006
667458141149548307
2127932992585026491
4...

result:

wrong answer 7th lines differ - expected: '1164835025329039520', found: '1184240922443768439'