QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729283 | #9520. Concave Hull | am_i | WA | 32ms | 3820kb | C++20 | 5.6kb | 2024-11-09 16:49:57 | 2024-11-09 16:49:57 |
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].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'