QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #425996 | #8669. 正方形计数 | schrodingerstom | 10 | 392ms | 4064kb | C++14 | 7.9kb | 2024-05-30 20:05:38 | 2024-05-30 20:05:40 |
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) {
assert(v>0);
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);
// debug("up = %lld, dn = %lld\n",up,dn);
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);
// debug("up = %lld, dn = %lld\n",up,dn);
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);
// debug("up = %lld, dn = %lld\n",up,dn);
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);
}
bool lower(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) {
assert(c>0);
if(abs(b)>=c) {
ll whole=b/c;
return (n+1)*whole+calc(n,a,b-whole*c,c);
}
if(b<0) {
return -(n+1)+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+1);
ll m=(a*n+b)/c;
return (m+1)*(n+1)-calc(m,c,-b+a-1,a);
}
constexpr int V=2000;
// constexpr int V=10;
constexpr int maxn=15;
int n;
point pt[maxn];
ray ln[maxn],que[maxn];
pii half_plane() {
// for(int i=0;i<n;i++) {
// debug("(%lld, %lld) -> (%lld, %lld)\n",ln[i].o.x,ln[i].o.y,ln[i].d.x,ln[i].d.y);
// }
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};
// debug("tead = %d, rail = %d\n",tead,rail);
if(!cross(que[tead].d,que[tead+1].d)) return {0,0};
// debug("tead = %d, rail = %d\n",tead,rail);
for(int i=tead;i<rail;i++) if(upper(que[tead],que[tead+1],que[i])) {
// debug("tead = %d, i = %d\n",tead,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 i=1;i<=1;i++) {
// for(int j=1;j<=1;j++) {
// debug("---------------i = %d, j = %d----------------\n",i,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(i==0&&j==1) {
// debug("L = %d, R = %d\n",L,R);
// }
if(L==R) continue;
// if(i==0&&j==1) {
// debug("L = %d, R = %d\n",L,R);
// }
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]);
// debugln("k = %d, l = %lld, r = %lld\n",k,l,r);
if(l>r) continue;
// ret-=calc(r-l,que[k].d.y,-que[k].d.y*que[k].o.x+que[k].d.x*que[k].o.y-1,que[k].d.x);
ret-=calc(r-l,que[k].d.y,cross(que[k].d,que[k].o)-1+l*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]);
// debugln("k = %d, l = %lld, r = %lld\n",k,l,r);
if(l>r) continue;
ret+=calc(r-l,que[k].d.y,cross(que[k].o,que[k].d)-r*que[k].d.y,-que[k].d.x);
}
}
// debug("ret = %lld\n",ret);
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]);
// debugln("k = %d, l = %lld, r = %lld\n",k,l,r);
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]));
// debugln("k = %d\n",k);
// ret+=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]));
// debugln("k = %d\n",k);
// ret-=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;
}
// goto edn;
}
}
edn:;
printf("%lld\n",ret);
return 0;
}
/*
g++ template.cpp -o template -std=c++14 -Wall -Wextra -Wshadow -fsanitize=address,undefined
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 224ms
memory: 3968kb
input:
4 131 603 131 1828 1919 1828 1919 603
output:
361182910200
result:
ok 1 number(s): "361182910200"
Test #2:
score: 0
Accepted
time: 119ms
memory: 3904kb
input:
4 239 211 239 962 261 962 261 211
output:
1498772
result:
ok 1 number(s): "1498772"
Test #3:
score: 0
Accepted
time: 392ms
memory: 4064kb
input:
4 0 0 0 2000 2000 2000 2000 0
output:
1336001667000
result:
ok 1 number(s): "1336001667000"
Test #4:
score: 0
Accepted
time: 120ms
memory: 3812kb
input:
4 36 771 36 786 672 786 672 771
output:
427720
result:
ok 1 number(s): "427720"
Test #5:
score: 0
Accepted
time: 121ms
memory: 3872kb
input:
4 0 100 100 200 200 100 100 0
output:
34001650
result:
ok 1 number(s): "34001650"
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 151ms
memory: 3824kb
input:
3 131 603 131 1828 1919 603
output:
63864307980
result:
wrong answer 1st numbers differ - expected: '63739309181', found: '63864307980'
Subtask #3:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%