QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#426098 | #8669. 正方形计数 | schrodingerstom | 100 ✓ | 956ms | 4132kb | C++14 | 6.3kb | 2024-05-30 20:59:09 | 2024-05-30 20:59:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define debug(fmt,...) fprintf(stderr, fmt,##__VA_ARGS__)
#define debugln(fmt,...) fprintf(stderr,"[%d] " fmt,__LINE__,##__VA_ARGS__)
#define TIME (1e3*clock()/CLOCKS_PER_SEC)
bool memBeg;
template<typename T> void chkmin(T &x,T y) {x=min(x,y);}
template<typename T> void chkmax(T &x,T y) {x=max(x,y);}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,ll times,int ret=1) {
for(;times;times>>=1,x=1ll*x*x%mod) if(times&1) ret=1ll*ret*x%mod;
return ret;
}
struct point {
ll x,y;
point() {}
point(ll _x,ll _y): x(_x),y(_y) {}
point operator+(const point &o) const {return point(x+o.x,y+o.y);}
point operator-(const point &o) const {return point(x-o.x,y-o.y);}
point operator*(ll o) const {return point(x*o,y*o);}
friend point operator*(ll u,const point &v) {return v*u;}
friend ll dot(const point &u,const point &v) {return u.x*v.x+u.y*v.y;}
friend ll cross(const point &u,const point &v) {return u.x*v.y-u.y*v.x;}
point operator~() const {return point(-y,x);}
};
struct ray {
point o,d;
ray() {}
ray(const point &_o,const point &_d): o(_o),d(_d) {}
};
ll div_dn(ll u,ll v) {
if(u>=0) return u/v;
return -((-u+v-1)/v);
}
int crossl(const ray &l1,const ray &l2) {
ll up=cross(l2.o-l1.o,l2.d)*l1.d.x,dn=cross(l1.d,l2.d);
return l1.o.x+div_dn(up-1,dn);
}
int crossd(const ray &l1,const ray &l2) {
ll up=cross(l2.o-l1.o,l2.d)*l1.d.x,dn=cross(l1.d,l2.d);
return l1.o.x+div_dn(up,dn);
}
int crossr(const ray &l1,const ray &l2) {
ll up=cross(l2.o-l1.o,l2.d)*l1.d.x,dn=cross(l1.d,l2.d);
return l1.o.x+div_dn(up,dn)+1;
}
int crossu(const ray &l1,const ray &l2) {
ll up=cross(l2.o-l1.o,l2.d)*l1.d.x,dn=cross(l1.d,l2.d);
return l1.o.x+div_dn(up+dn-1,dn);
}
int cross0(const ray &l1,const ray &l2) {
ll up=cross(l2.o-l1.o,l2.d)*l1.d.y,dn=cross(l1.d,l2.d);
return l1.o.y+div_dn(up-1,dn);
}
int cross1(const ray &l1,const ray &l2) {
ll up=cross(l2.o-l1.o,l2.d)*l1.d.y,dn=cross(l1.d,l2.d);
return l1.o.y+div_dn(up,dn);
}
int quadrant(const point &o) {
return (o.y<0)<<1|((o.x<0)^(o.y<0));
}
bool check_anti(const point &u,const point &v) {
return cross(u,v)>0;
}
bool polar_cmp(const point &u,const point &v) {
int pu=quadrant(u),pv=quadrant(v);
if(pu!=pv) return pu<pv;
return check_anti(u,v);
}
bool upper(const ray &l1,const ray &l2,const ray &l3) {
return cross(l2.o-l1.o,l2.d)*cross(l1.d,l3.d)>cross(l3.o-l1.o,l3.d)*cross(l1.d,l2.d);
}
ll calc(ll n,ll a,ll b,ll c) {
if(abs(b)>=c) {
ll whole=b/c;
return n*whole+calc(n,a,b-whole*c,c);
}
if(b<0) {
return -n+calc(n,a,b+c,c);
}
if(abs(a)>=c) {
ll whole=a/c;
return n*(n+1)/2*whole+calc(n,a-whole*c,b,c);
}
if(a<0) {
return -n*(n+1)/2+calc(n,a+c,b,c);
}
if(a==0) return b/c*n;
ll m=(a*n+b)/c;
return m*(n+1)-calc(m,c,-b+a-1,a);
}
constexpr int V=2000;
constexpr int maxn=15;
int n;
point pt[maxn];
ray ln[maxn],que[maxn];
pii half_plane() {
int tead=1,rail=1;
for(int i=0;i<n;i++) {
while(rail-tead>1&&upper(que[rail-2],que[rail-1],ln[i])) rail--;
while(rail-tead>1&&upper(que[tead],que[tead+1],ln[i])) tead++;
que[rail++]=ln[i];
}
while(rail-tead>2&&upper(que[rail-2],que[rail-1],que[tead])) rail--;
if(rail-tead<=2) return {0,0};
if(cross(que[tead].d,que[tead+1].d)<=0) return {0,0};
for(int i=0;i<n;i++) if(upper(que[tead],que[tead+1],ln[i])) return {0,0};
return {tead,rail};
}
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
debug("%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
#ifdef LOCAL
freopen("debug","w",stderr);
#endif
scanf("%d",&n);
for(int i=0;i<n;i++) {
scanf("%lld%lld",&pt[i].x,&pt[i].y);
}
reverse(pt,pt+n); pt[n]=pt[0];
ll ret=0;
for(int i=0;i<=V;i++) {
for(int j=1;i+j<=V;j++) {
for(int k=0;k<n;k++) {
point d=pt[k+1]-pt[k],o=pt[k],v(i,j);
for(point no:{pt[k]+v,pt[k]+~v,pt[k]+v+~v}) {
if(check_anti(d,no-o)) o=no;
}
ln[k]=ray(o,d);
}
int L,R; tie(L,R)=half_plane();
if(L==R) continue;
que[L-1]=que[R-1]; que[R]=que[L];
for(int k=L;k<R;k++) {
if(que[k].d.x>0) {
ll l=crossr(que[k-1],que[k]),r=crossl(que[k],que[k+1]);
if(l>r) continue;
ret-=calc(r-l+1,que[k].d.y,cross(que[k].d,que[k].o)-1+l*que[k].d.y-que[k].d.y,que[k].d.x);
} else if(que[k].d.x<0) {
ll r=crossl(que[k-1],que[k]),l=crossr(que[k],que[k+1]);
if(l>r) continue;
ret+=calc(r-l+1,-que[k].d.y,cross(que[k].o,que[k].d)-(l-1)*que[k].d.y,-que[k].d.x);
}
}
vector<pii> dn;
for(int k=L;k<R;k++) {
ll l=crossd(que[k],que[k+1]),r=crossu(que[k],que[k+1]);
if(l<r) continue;
if(que[k].d.x>0||(que[k].d.x==0&&que[k].d.y<0)) {
if(que[k+1].d.x<0) {
dn.emplace_back(l,cross1(que[k],que[k+1]));
}
dn.emplace_back(l,-cross0(que[k],que[k+1]));
} else {
if(que[k+1].d.x>0) {
dn.emplace_back(l,-cross0(que[k],que[k+1]));
}
dn.emplace_back(l,cross1(que[k],que[k+1]));
}
}
sort(dn.begin(),dn.end());
for(int k=0;k<(int)dn.size();k++) {
if(!k||dn[k]!=dn[k-1]) ret+=dn[k].second;
}
}
}
printf("%lld\n",ret);
return 0;
}
/*
g++ template.cpp -o template -std=c++14 -Wall -Wextra -Wshadow -fsanitize=address,undefined
*/
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 216ms
memory: 3992kb
input:
4 131 603 131 1828 1919 1828 1919 603
output:
361182910200
result:
ok 1 number(s): "361182910200"
Test #2:
score: 10
Accepted
time: 110ms
memory: 4120kb
input:
4 239 211 239 962 261 962 261 211
output:
1498772
result:
ok 1 number(s): "1498772"
Test #3:
score: 10
Accepted
time: 387ms
memory: 3892kb
input:
4 0 0 0 2000 2000 2000 2000 0
output:
1336001667000
result:
ok 1 number(s): "1336001667000"
Test #4:
score: 10
Accepted
time: 109ms
memory: 3908kb
input:
4 36 771 36 786 672 786 672 771
output:
427720
result:
ok 1 number(s): "427720"
Test #5:
score: 10
Accepted
time: 108ms
memory: 3836kb
input:
4 0 100 100 200 200 100 100 0
output:
34001650
result:
ok 1 number(s): "34001650"
Subtask #2:
score: 25
Accepted
Test #6:
score: 25
Accepted
time: 135ms
memory: 3840kb
input:
3 131 603 131 1828 1919 603
output:
63739309181
result:
ok 1 number(s): "63739309181"
Test #7:
score: 25
Accepted
time: 87ms
memory: 4092kb
input:
3 239 211 239 962 261 211
output:
353073
result:
ok 1 number(s): "353073"
Test #8:
score: 25
Accepted
time: 166ms
memory: 3844kb
input:
3 0 0 0 2000 2000 0
output:
222889277611
result:
ok 1 number(s): "222889277611"
Test #9:
score: 25
Accepted
time: 80ms
memory: 3892kb
input:
3 36 771 36 786 672 771
output:
98847
result:
ok 1 number(s): "98847"
Test #10:
score: 25
Accepted
time: 80ms
memory: 3844kb
input:
3 0 0 0 100 100 0
output:
1473186
result:
ok 1 number(s): "1473186"
Subtask #3:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 227ms
memory: 3908kb
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
4047
result:
ok 1 number(s): "4047"
Test #12:
score: 15
Accepted
time: 241ms
memory: 4116kb
input:
8 0 4 1 15 2 15 15 14 15 4 14 0 1 0 0 2
output:
4200
result:
ok 1 number(s): "4200"
Test #13:
score: 15
Accepted
time: 139ms
memory: 3808kb
input:
5 7 15 15 13 15 0 3 0 0 15
output:
3635
result:
ok 1 number(s): "3635"
Test #14:
score: 15
Accepted
time: 227ms
memory: 3892kb
input:
8 0 12 2 14 7 15 13 15 15 10 15 1 8 0 0 0
output:
4511
result:
ok 1 number(s): "4511"
Test #15:
score: 15
Accepted
time: 163ms
memory: 3832kb
input:
6 0 11 3 15 7 15 15 12 10 0 0 0
output:
3006
result:
ok 1 number(s): "3006"
Test #16:
score: 15
Accepted
time: 145ms
memory: 3836kb
input:
5 0 0 0 2 1 2 2 1 2 0
output:
4
result:
ok 1 number(s): "4"
Subtask #4:
score: 20
Accepted
Dependency #3:
100%
Accepted
Test #17:
score: 20
Accepted
time: 249ms
memory: 4128kb
input:
8 49 299 144 300 300 260 250 15 115 0 30 0 23 19 0 85
output:
443602646
result:
ok 1 number(s): "443602646"
Test #18:
score: 20
Accepted
time: 245ms
memory: 3836kb
input:
8 0 133 103 300 130 300 257 294 297 227 300 150 277 40 161 4
output:
351466521
result:
ok 1 number(s): "351466521"
Test #19:
score: 20
Accepted
time: 248ms
memory: 3772kb
input:
8 76 286 114 300 300 300 300 205 291 0 47 0 4 57 2 235
output:
605026927
result:
ok 1 number(s): "605026927"
Test #20:
score: 20
Accepted
time: 247ms
memory: 3776kb
input:
8 0 102 40 274 282 300 300 234 267 0 34 0 6 57 0 86
output:
497330741
result:
ok 1 number(s): "497330741"
Test #21:
score: 20
Accepted
time: 209ms
memory: 3928kb
input:
7 0 288 156 300 212 300 265 176 300 86 278 0 0 36
output:
446722651
result:
ok 1 number(s): "446722651"
Subtask #5:
score: 15
Accepted
Dependency #4:
100%
Accepted
Test #22:
score: 15
Accepted
time: 196ms
memory: 3844kb
input:
5 257 800 766 800 800 353 667 0 42 0
output:
18881369614
result:
ok 1 number(s): "18881369614"
Test #23:
score: 15
Accepted
time: 309ms
memory: 3912kb
input:
8 691 800 737 795 800 651 372 98 136 266 118 318 24 629 12 753
output:
8760058886
result:
ok 1 number(s): "8760058886"
Test #24:
score: 15
Accepted
time: 270ms
memory: 3924kb
input:
8 718 800 740 800 800 726 800 670 711 367 595 150 86 0 57 136
output:
3064355626
result:
ok 1 number(s): "3064355626"
Test #25:
score: 15
Accepted
time: 315ms
memory: 4128kb
input:
8 0 347 16 449 364 798 674 800 750 800 797 14 195 0 0 70
output:
23587042437
result:
ok 1 number(s): "23587042437"
Test #26:
score: 15
Accepted
time: 355ms
memory: 3844kb
input:
8 322 800 596 800 686 777 800 280 764 69 396 0 46 179 0 660
output:
23185884331
result:
ok 1 number(s): "23185884331"
Subtask #6:
score: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #27:
score: 15
Accepted
time: 814ms
memory: 3892kb
input:
8 0 1150 314 2000 1101 2000 1617 1607 1778 551 738 0 607 10 0 1011
output:
577130875850
result:
ok 1 number(s): "577130875850"
Test #28:
score: 15
Accepted
time: 868ms
memory: 4096kb
input:
8 0 1841 1526 2000 1981 1680 1968 678 1893 26 973 0 616 315 524 434
output:
735496008519
result:
ok 1 number(s): "735496008519"
Test #29:
score: 15
Accepted
time: 680ms
memory: 3992kb
input:
6 0 258 10 2000 1730 2000 2000 1510 1973 0 0 129
output:
1203935109430
result:
ok 1 number(s): "1203935109430"
Test #30:
score: 15
Accepted
time: 773ms
memory: 4116kb
input:
7 200 2000 1686 2000 1951 1878 2000 863 1422 0 21 0 0 1015
output:
1100462975231
result:
ok 1 number(s): "1100462975231"
Test #31:
score: 15
Accepted
time: 956ms
memory: 3836kb
input:
8 701 2000 1449 2000 1847 1928 2000 1496 1987 668 1588 108 263 0 0 1985
output:
997591862206
result:
ok 1 number(s): "997591862206"
Test #32:
score: 15
Accepted
time: 849ms
memory: 4132kb
input:
8 15 2000 1235 2000 1545 1886 1970 1526 1828 427 1238 97 372 0 0 1786
output:
816089046494
result:
ok 1 number(s): "816089046494"
Test #33:
score: 15
Accepted
time: 681ms
memory: 3832kb
input:
7 0 1685 1331 2000 2000 1941 2000 1310 1757 631 21 113 0 575
output:
633230324466
result:
ok 1 number(s): "633230324466"
Test #34:
score: 15
Accepted
time: 681ms
memory: 3888kb
input:
8 0 650 0 1350 650 2000 1350 2000 2000 1350 2000 650 1350 0 650 0
output:
900037062925
result:
ok 1 number(s): "900037062925"