QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412033#8669. 正方形计数dingdingtang11514#60 1978ms3912kbC++143.8kb2024-05-15 23:26:162024-05-15 23:26:17

Judging History

你现在查看的是最新测评结果

  • [2024-05-15 23:26:17]
  • 评测
  • 测评结果:60
  • 用时:1978ms
  • 内存:3912kb
  • [2024-05-15 23:26:16]
  • 提交

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%