QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#683761 | #9520. Concave Hull | KavenSky | AC ✓ | 153ms | 19448kb | C++23 | 10.1kb | 2024-10-27 23:30:24 | 2024-10-30 01:33:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000005
#define INF 1e8
#define none -1145141919810
#define ls p<<1
#define rs p<<1|1
typedef pair<int,int>Pl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>Pll;
const ll mod=1e9+7;
typedef long long db;
const db pi=acosl(-1.0);
const db eps=0;
const db g=9.8;
int sign(db a){return a<-eps?-1:a>eps;}
int cmp(db a,db b){return sign(a-b);}
struct P{
db x,y;
P(db x=0,db y=0):x(x),y(y){}
P operator+(P p){return {x+p.x,y+p.y};}
P operator-(P p){return {x-p.x,y-p.y};}
P operator*(db d){return {x*d,y*d};}
P operator/(db d){return{x/d,y/d};}
bool operator<(P p){
int c=cmp(x,p.x);
if(c) return c==-1;
return cmp(y,p.y)==-1;
}
bool operator==(P o){
return cmp(x,o.x)==0&&cmp(y,o.y)==0;
}
bool operator!=(P o){
return cmp(x,o.x)!=0||cmp(y,o.y)!=0;
}
int quad()const{return sign(y)==1||(sign(y)==0&&sign(x)>=0);}
db dot(P p){return x*p.x+y*p.y;}
db det(P p){return x*p.y-y*p.x;}
db abs1(){return sqrt(abs2());}
db abs2(){return x*x+y*y;}
db disTo(P p){return (*this-p).abs1();}
db disTo2(P p){return (*this-p).abs2();}
P rot90(){return P(-y,x);}
P unit(){return *this/abs1();}
P rot(db an){return {x*cos(an)-y*sin(an),x*sin(an)+y*cos(an)};}
db alpha(){return atan2l(y,x);}
};
db cross(P p1,P p2,P p3){return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);}
db crossop(P p1,P p2,P p3){return sign(cross(p1,p2,p3));}
db rad(P p1,P p2){return atan2l(p1.det(p2),p1.dot(p2));}
bool cheLL(P p1,P p2,P q1,P q2){
db a1=cross(q1,q2,p1),a2=-cross(q1,q2,p2);
return sign(a1+a2)!=0;
}
P isLL(P p1,P p2,P q1, P q2){
db a1=cross(q1,q2,p1),a2=-cross(q1,q2,p2);
return (p1*a2+p2*a1)/(a1+a2);
}
bool intersect(db l1,db r1,db l2,db r2){
if(l1>r1) swap(l1,r1);
if(l2>r2) swap(l2,r2);
return !(cmp(r1,l2)==-1||cmp(r2,l1)==-1);
}
bool isSS(P p1,P p2,P q1,P q2){
return intersect(p1.x,p2.x,q1.x,q2.x)&&intersect(p1.y,p2.y,q1.y,q2.y)&&crossop(p1,p2,q1)*crossop(p1,p2,q2)<=0&&crossop(q1,q2,p1)*crossop(q1,q2,p2)<=0;
}
bool isSS_strict(P p1,P p2,P q1,P q2){
return crossop(p1,p2,q1)*crossop(p1,p2,q2)<0&&crossop(q1,q2,p1)*crossop(q1,q2,p2)<0;
}
bool ismiddle(db a,db b, db m){
return sign(a-m)==0||sign(b-m)==0||(a<m)!=(b<m);
}
bool ismiddle(P a,P b,P m){
return ismiddle(a.x,b.x,m.x)&&ismiddle(a.y,b.y,m.y);
}
bool onseg(P p1,P p2, P q){
return crossop(p1,p2,q)==0&&ismiddle(p1,p2,q);
}
bool onseg_strict(P p1,P p2,P q){
return crossop(p1,p2,q)==0&&sign((q-p1).dot(p1-p2))*sign((q-p2).dot(p1-p2))<0;
}
P proj(P p1,P p2,P q){
P dir=p2-p1;
return p1+dir*(dir.dot(q-p1)/dir.abs2());
}
P refle(P p1,P p2,P q){
return proj(p1,p2,q)*2-q;
}
db nearest(P p1,P p2,P q){
if(p1==p2) return p1.disTo(q);
P h=proj(p1,p2,q);
if(ismiddle(p1,p2,h)){
return q.disTo(h);
}
return min(p1.disTo(q),p2.disTo(q));
}
db disSS(P p1,P p2,P q1,P q2){
if(isSS(p1,p2,q1,q2)) return 0;
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)),min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
bool cmp(P a,P b){
int qa=a.quad(),qb=b.quad();
if(qa!=qb) return qa<qb;
else return sign(a.det(b))>0;
}
db area(vector<P>&ps){
db ans=0;
int n=ps.size();
for(int i=0;i<n;i++){
ans+=ps[i].det(ps[(i+1)%n]);
}
return ans;
}
int contain(vector<P>&ps,P p){
int n=ps.size();
int ret=0;
for(int i=0;i<n;i++){
P u=ps[i],v=ps[(i+1)%n];
if(onseg(u,v,p)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(p.y,u.y)>0||cmp(p.y,v.y)<=0) continue;
ret^=crossop(p,u,v)>0;
}
return ret*2;
}
vector<P>convexHull(vector<P>&ps){
int n=ps.size();if(n<=1) return ps;
sort(ps.begin(),ps.end());
vector<P>qs(n*2);
int k=0;
for(int i=0;i<n;qs[k++]=ps[i++]){
while(k>1&&crossop(qs[k-2],qs[k-1],ps[i])<=0) k--;
}
for(int i=(n-2),t=k;i>=0;qs[k++]=ps[i--]){
while(k>t&&crossop(qs[k-2],qs[k-1],ps[i])<=0) k--;
}
qs.resize(k-1);
return qs;
}
db convexDiameter(vector<P>&ps){
int n=ps.size(); if(n<=1) return 0;
int is=0,js=0;
for(int i=1;i<n;i++){
is=ps[i]<ps[is]?i:is;
js=ps[js]<ps[i]?i:js;
}
db ret=ps[is].disTo(ps[js]);
int i=is,j=js;
do{
if((ps[(i+1)%n]-ps[i]).det((ps[(j+1)%n]-ps[j]))>=0) (++j)%=n;
else (++i)%=n;
ret=max(ret,ps[i].disTo(ps[j]));
}while(i!=is||j!=js);
return ret;
}
vector<P> convexCut(const vector<P>&ps,P q1,P q2){
vector<P>qs;
int n=ps.size();
for(int i=0;i<n;i++){
P p1=ps[i],p2=ps[(i+1)%n];
int d1=crossop(q1,q2,p1),d2=crossop(q1,q2,p2);
if(d1>=0) qs.push_back(p1);
if(d1*d2<0) qs.push_back(isLL(p1,p2,q1,q2));
}
return qs;
}
vector<P>convexHullStrict(vector<P>&ps){
int n=ps.size();if(n<=1) return ps;
sort(ps.begin(),ps.end());
n=unique(ps.begin(),ps.end())-ps.begin();
vector<P>qs(n*2);
int k=0;
for(int i=0;i<n;qs[k++]=ps[i++]){
while(k>1&&crossop(qs[k-2],qs[k-1],ps[i])<0) k--;
}
for(int i=(n-2),t=k;i>=0;qs[k++]=ps[i--]){
while(k>t&&crossop(qs[k-2],qs[k-1],ps[i])<0) k--;
}
qs.resize(k-1);
return qs;
}
int type(P o1,db r1,P o2,db r2){
db d=o1.disTo(o2);
if(cmp(d,r1+r2)==1) return 4;
if(cmp(d,r1+r2)==0) return 3;
if(cmp(d,abs(r1-r2))==1) return 2;
if(cmp(d,abs(r1-r2))==0) return 1;
return 0;
}
vector<P> isCL(P o,db r,P p1,P p2){ //圆和线段
if(cmp(abs((o-p1).det(p2-p1))/p1.disTo(p2),r)>0) return {};
db x=(p1-o).dot(p2-p1),y=(p2-p1).abs2(),d=x*x-y*((p1-o).abs2()-r*r);
d=max(d,(db)0.0);
P m=p1-(p2-p1)*(x/y),dr=(p2-p1)*(sqrt(d)/y);
return {m-dr,m+dr};
}
vector<P> isCC(P o1,db r1,P o2,db r2){ //圆和圆
db d=o1.disTo(o2);
if(cmp(d,r1+r2)==1) return {};
if(cmp(d,abs(r1-r2))==-1) return {};
d=min(d,r1+r2);
db y=(r1*r1+d*d-r2*r2)/(2*d),x=sqrt(r1*r1-y*y);
P dr=(o2-o1).unit();
P q1=o1+dr*y,q2=dr.rot90()*x;
return {q1-q2,q1+q2};
}
//intanCC:-r2,tanCP r2=0
vector<pair<P,P>> tanCC(P o1,db r1,P o2,db r2){
P d=o2-o1;
db dr=r1-r2,d2=d.abs2(),h2=d2-dr*dr;
if(sign(d2)==0||sign(h2)<0) return {};
h2=max((db)0.0,h2);
vector<pair<P,P>>ret;
for(db sign:{-1,1}){
P v=(d*dr+d.rot90()*sqrt(h2)*sign)/d2;
ret.push_back({o1+v*r1,o2+v*r2});
}
if(sign(h2)==0) ret.pop_back();
return ret;
}
P inCenter(P A,P B,P C){
db a=(B-C).abs1(),b=(C-A).abs1(),c=(A-B).abs1();
return (A*a+B*b+C*c)/(a+b+c);
}
P circumCenter(P A,P B,P C){
P bb=B-A,cc=C-A;
db da=bb.abs2(),dc=cc.abs2(),d=2*bb.det(cc);
return A-P(bb.y*dc-cc.y*da,cc.x*da-bb.x*dc)/d;
}
P othroCenter(P a,P b,P c){
P ba=b-a,ca=c-a,bc=b-c;
db Y=ba.y*ca.y*bc.y,
A=ca.det(ba),
x0=(Y+ca.x*ba.y*b.x-ba.x*ca.y*c.x)/A,
y0=-ba.x*(x0-c.x)/ba.y+ca.y;
return {x0,y0};
}
pair<P,db> min_circle(vector<P>&ps){
random_shuffle(ps.begin(),ps.end());
int n=ps.size();
P o=ps[0];db r=0;
for(int i=1;i<n;i++){
if(o.disTo(ps[i])>r+eps){
o=ps[i],r=0;
for(int j=0;j<i;j++){
if(o.disTo(ps[j])>eps+r){
o=(ps[i]+ps[j])/2;
r=o.disTo(ps[i]);
for(int k=0;k<j;k++){
if(o.disTo(ps[k])>r+eps){
o=circumCenter(ps[i],ps[j],ps[k]);
r=o.disTo(ps[i]);
}
}
}
}
}
}
return {o,r};
}
vector<P>minkowski(vector<P>ps,vector<P>qs){
int n=ps.size(),m=qs.size();
vector<P>s1(n),s2(m);
for(int i=0;i<n;i++) s1[i]=ps[(i+1)%n]-ps[i];
for(int i=0;i<m;i++) s2[i]=qs[(i+1)%m]-qs[i];
vector<P>Q;
Q.push_back(ps[0]+qs[0]);
int i=0,j=0;
while(i<n&&j<m){
if(s1[i].det(s2[j])>=0) Q.push_back(Q.back()+s1[i++]);
else Q.push_back(Q.back()+s2[j++]);
}
while(i<n) Q.push_back(Q.back()+s1[i++]);
while(j<m) Q.push_back(Q.back()+s2[j++]);
return Q;
}
bool inConvex(vector<P>&ps,P p){
int n=ps.size();
int l=0,r=n-1;
while(l+1<r){
int mid=(l+r)/2;
db A=crossop(ps[0],ps[mid],p);
db B=crossop(ps[0],ps[(mid+1)],p);
if(A>=0&&B<=0){
if(crossop(ps[mid],ps[mid+1],p)>=0) return true;
return false;
}
else if(A<0) r=mid;
else l=mid;
}
return false;
}
void solve(){
int n;
cin >> n;
vector<P>ps(n),qs,Qs;
map<Pll,int>mp;
for(int i=0;i<n;i++){
cin >> ps[i].x >> ps[i].y;
mp[{ps[i].x,ps[i].y}]++;
}
qs=convexHullStrict(ps);
db ANS=area(qs);
//ANS*=2;
for(int i=0;i<qs.size();i++){
mp[{qs[i].x,qs[i].y}]--;
}
for(int i=0;i<n;i++){
if(mp[{ps[i].x,ps[i].y}]){ Qs.push_back({ps[i]});
mp[{ps[i].x,ps[i].y}]--;
}
}
if(!Qs.size()){
cout << -1 << "\n";
return;
}
Qs=convexHullStrict(Qs);
db MX=3e18;
int a=Qs.size();
int b=qs.size();
auto S=[&](int i,int j){
return abs(cross(Qs[i],qs[j],qs[(j+1)%b]));
};
auto nxt=[&](int i){
return (i+1+a)%a;
};
auto las=[&](int i){
return (i+a-1)%a;
};
int j=0;
for(int i=0;i<a;i++){
if(S(i,0)<MX){
MX=S(i,0);
j=i;
}
}
//cerr << Qs[1].x << " " << Qs[1].y << " " << ps[0].x << " " << ps[0].y << " " << ps[1].x << " " << ps[1].y << "\n";
for(int i=0;i<b;i++){
while(S(nxt(j),i)<S(j,i)) j=nxt(j);
while(S(las(j),i)<S(j,i)) j=las(j);
MX=min(MX,S(j,i));
}
//cerr << MX << "\n";
cout << ANS-MX << "\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(0);
int t=1;
cin >> t;
while(t--)
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3648kb
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: 3680kb
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: 0
Accepted
time: 43ms
memory: 3688kb
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 1164835025329039520 1527446155241140517 1807368432185303666 1236918659444944569 1306839249967484778 1984123720246784099 1868728080720036006 667458140583450322 2127932992585026491 4...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 45ms
memory: 3820kb
input:
10000 9 484630042 51929469 -40468396 -517784096 98214104 -103353239 629244333 -475172587 106398764 153884485 49211709 -44865749 1 10 166321833 -247717657 406208245 668933360 13 548702216 -631976459 37150086 -292461024 707804811 -486185860 239775286 -903166050 10096571 -541890068 686103484 558731937 ...
output:
950319193795831919 1661025342421008544 1285164852091455548 1159924751776806668 1206071151805176722 794021230296144371 699991678992587791 1133990718508584290 1486311831172661605 984875884297072200 1327767982175057345 758247019006396699 1355381234262206155 1139262078529131471 1613462877860621700 12392...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 99ms
memory: 4660kb
input:
100 439 471536154 -312612104 155692036 -937312180 -461624056 -357636609 236656684 -911414873 -288656914 -74788431 -465779694 -381475149 -334197401 -903065737 491513067 -447615916 337664889 -852236281 -281689379 -53519178 -159101704 -920779200 -326159514 -95396204 21868593 -994282736 488425383 -41046...
output:
1973162724053130487 2054612790507830954 1726805687754843724 1699420177872986528 2129388571309147631 2198295137903288810 1697185883164440272 1219697450095721478 2027023581922285255 1674691247127206655 1673105966817209954 2179188692918747442 2146544318743443141 2230356305133660648 1676850321902993764 ...
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 79ms
memory: 4680kb
input:
100 1362 -467257672 -466669 -467054869 -478108 -466973270 -481776 -466556983 -499770 -466329414 -508693 -466248017 -511805 -466158865 -513786 -466101273 -515035 -465927700 -518748 -465717624 -522106 -465303448 -528127 -465124548 -530726 -464649746 -536693 -464554872 -537799 -464478196 -538680 -46416...
output:
1666097696993497 1791366071767866 1806187278469532 1683419854733713 1685891971828916 1730190225081651 1787048201197565 1850308098208660 1710694884375502 1826363113637639 1816375352374659 2047431269497691 1549806516003854 1829438662895747 1678707854135065 1687423392883819 2121960009997761 16687219538...
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 50ms
memory: 12140kb
input:
2 62666 -486101704 -505730259 -486101698 -506082699 -486101689 -506111362 -486101682 -506126031 -486101528 -506293759 -486101259 -506556385 -486101196 -506613483 -486101154 -506648604 -486100935 -506831392 -486100631 -507083675 -486100470 -507199151 -486100233 -507368923 -486100193 -507397039 -48609...
output:
2178736946152219010 1825181940245096152
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 153ms
memory: 19448kb
input:
2 100000 301945097 76373292 467957663 -286424714 8245445 -597212507 -474204621 -708828667 184159460 105942538 443435905 -429212625 490658771 -382198656 82512047 -612522436 -228221388 -965890088 394789011 -145801151 -106120174 -528202395 428939626 -194437311 497429477 -527407728 365739746 -114818962 ...
output:
2502889432701099511 2267250485735988121
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 128ms
memory: 17484kb
input:
2 100000 221128057 -975244780 -618765360 -785575858 422567455 -906331476 -988680318 -150037424 -929870145 367887908 -757813541 -652471177 291995621 -956419655 -785381507 619012026 468864522 -883270094 -588416522 808557973 859345881 511394814 988105866 153775152 216931298 -976186873 467050734 8842305...
output:
6283183114882825575 6283183188903854361
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
7 5 -1000000000 -1000000000 1000000000 -1000000000 1000000000 1000000000 1 0 -1 0 5 1000000000 1000000000 -1000000000 -1000000000 -2 0 -1 0 1 -1 6 1000000000 1000000000 -1000000000 -1000000000 -3 0 -1 0 0 -1 1 -1 4 -1000000000 -1000000000 1000000000 -1000000000 1000000000 1000000000 -1000000000 1000...
output:
4000000000000000000 7000000000 9000000001 -1 6000000002000000000 7999999998000000000 -1
result:
ok 7 lines
Extra Test:
score: 0
Extra Test Passed