QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412033 | #8669. 正方形计数 | dingdingtang11514# | 60 | 1978ms | 3912kb | C++14 | 3.8kb | 2024-05-15 23:26:16 | 2024-05-15 23:26:17 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>
//
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it])
#define In __inline
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
// mt19937_64 wql(514);
In int read() {
ll x=1,a=0;
char ch=getchar();
while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
return a*x;
} const int N=10,M=2005;
int n;
struct point {
int x,y;
point(int a=0,int b=0){x=a,y=b;}
} a[N];
point OP + (point x,point y) {
return point(x.x+y.x,x.y+y.y);
}
point OP - (point x,point y) {
return point(x.x-y.x,x.y-y.y);
}
int OP * (point x,point y) {
return x.x*y.y-y.x*x.y;
}
int area(point a0,point a1,point x) {
return (a1-a0)*(x-a0);
}
namespace S0 {
void solve0() {
int A=a[2].y-a[1].y,B=a[3].x-a[2].x;
int b=min(A,B),ret=0;
For(i,1,b) {
ret+=i*(A-i+1)*(B-i+1);
} printf("%lld\n",ret);
}
}
int mx,my;
namespace S1 {
int lowy[M],upy[M];
bool ans[M];
bool check(point x) {
int ret=area(a[n],a[1],x)<=0;
// printf("%lld ",area(a[n],a[1],x));
For(i,1,n-1) {
ret&=(area(a[i],a[i+1],x)<=0);
if(!ret) break;
}
return ret;
}
void solve1(){
int res=0;
memset(lowy,0x3f,sizeof lowy);
For(x,0,mx) {
For(y,0,my) {
ans[y]=check(point(x,y));
// printf("%d ",ans[y]);
}
// puts("");
int low=my+10,up=0;
For(i,0,my) {
if(ans[i]) low=min(low,i),up=max(up,i);
}
lowy[x]=low,upy[x]=up;
} For(a,1,mx) {
For(b,0,my) {
// if(!a && !b) continue;
For(x,0,mx) {
int x0=x,x1=x+a,x2=x+b,x3=x+a+b;
if(x3>mx) continue;
int low=max(max(lowy[x0]-b,lowy[x1]),max(lowy[x2]-a-b,lowy[x3]-a));
int up=min(min(upy[x0]-b,upy[x1]),min(upy[x2]-a-b,upy[x3]-a));
if(up>=low)res+=up-low+1;
// printf("%lld %lld %lld %lld\n",a,b,x,low);
}
}
}
printf("%lld",res);
}
}
namespace S2 {
int lowy[M],upy[M];
bool ans[M];
bool check(point x) {
int ret=area(a[n],a[1],x)<=0;
// printf("%lld ",area(a[n],a[1],x));
For(i,1,n-1) {
ret&=(area(a[i],a[i+1],x)<=0);
if(!ret) break;
}
return ret;
}
void solve2(){
int res=0;
memset(lowy,0x3f,sizeof lowy);
For(x,0,mx) {
For(y,0,my) {
ans[y]=check(point(x,y));
// printf("%d ",ans[y]);
}
// puts("");
int low=my+10,up=0;
For(i,0,my) {
if(ans[i]) low=min(low,i),up=max(up,i);
}
lowy[x]=low,upy[x]=up;
} For(a,1,mx) {
For(b,0,my) {
// if(!a && !b) continue;
For(x,0,mx) {
int x0=x,x1=x+a,x2=x+b,x3=x+a+b;
if(x3>mx) continue;
int low=max(max(lowy[x0]-b,lowy[x1]),max(lowy[x2]-a-b,lowy[x3]-a));
int up=min(min(upy[x0]-b,upy[x1]),min(upy[x2]-a-b,upy[x3]-a));
if(up>=low)res+=up-low+1;
else break;
// printf("%lld %lld %lld %lld\n",a,b,x,low);
}
}
}
printf("%lld",res);
}
}
signed main() {
n=read();
For(i,1,n) {
int x=read(),y=read();
a[i]=point(x,y);
mx=max(mx,x);my=max(my,y);
}
if(n==4 && a[1].x==a[2].x && a[2].y==a[3].y && a[3].x==a[4].x && a[4].y==a[1].y)
S0::solve0();
else if(n==3 && a[1].x==a[2].x && a[1].y==a[3].y)
S2::solve2();
else S1::solve1();
return 0;
}
}signed main() {
// freopen("name.in","r",stdin);
// freopen("name.out","w",stdout);
return Mine::main();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3888kb
input:
4 131 603 131 1828 1919 1828 1919 603
output:
361182910200
result:
ok 1 number(s): "361182910200"
Test #2:
score: 10
Accepted
time: 1ms
memory: 3772kb
input:
4 239 211 239 962 261 962 261 211
output:
1498772
result:
ok 1 number(s): "1498772"
Test #3:
score: 10
Accepted
time: 1ms
memory: 3728kb
input:
4 0 0 0 2000 2000 2000 2000 0
output:
1336001667000
result:
ok 1 number(s): "1336001667000"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3744kb
input:
4 36 771 36 786 672 786 672 771
output:
427720
result:
ok 1 number(s): "427720"
Test #5:
score: 10
Accepted
time: 9ms
memory: 3752kb
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: 1978ms
memory: 3760kb
input:
3 131 603 131 1828 1919 603
output:
0
result:
wrong answer 1st numbers differ - expected: '63739309181', found: '0'
Subtask #3:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 1ms
memory: 3804kb
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: 0ms
memory: 3744kb
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: 0ms
memory: 3848kb
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: 1ms
memory: 3744kb
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: 0ms
memory: 3716kb
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: 0ms
memory: 3684kb
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: 28ms
memory: 3912kb
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: 28ms
memory: 3748kb
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: 28ms
memory: 3804kb
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: 28ms
memory: 3668kb
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: 28ms
memory: 3788kb
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: 483ms
memory: 3840kb
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: 486ms
memory: 3756kb
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: 478ms
memory: 3704kb
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: 482ms
memory: 3728kb
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: 489ms
memory: 3840kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%