QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558385#8669. 正方形计数Take_A_Single_635 3329ms9968kbC++141.5kb2024-09-11 15:47:582024-09-11 15:48:01

Judging History

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

  • [2024-09-11 15:48:01]
  • 评测
  • 测评结果:35
  • 用时:3329ms
  • 内存:9968kb
  • [2024-09-11 15:47:58]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 1000000007
#define fir first
#define sec second
#define pr pair<int,int>
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX% 10 + '0');
}
int n,fx[maxn],fy[maxn],lx=1e9,ly=1e9,rx,ry,ans;
bool f[2005][2005];
bool cha(int x,int y,int X,int Y)
{
	return x*Y-X*y>=0;
}
bool check(int x,int y)
{
	for(int i=1;i<=n;i++)
		if(!cha(fy[i+1]-fy[i],fx[i+1]-fx[i],y-fy[i],x-fx[i]))return false;
	return true;
}
bool ck(int x,int y)
{
	if(x>=lx&&x<=rx&&y>=ly&&y<=ry&&f[x][y])return true;
	return false;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)fx[i]=read(),fy[i]=read(),lx=min(lx,fx[i]),rx=max(rx,fx[i]),ly=min(ly,fy[i]),ry=max(ry,fy[i]);
	fx[n+1]=fx[1],fy[n+1]=fy[1];
	for(int i=lx;i<=rx;i++)
		for(int j=ly;j<=ry;j++)f[i][j]=check(i,j);
	for(int i=lx;i<=rx;i++)
		for(int j=ly;j<=ry;j++)
		{
			if(!f[i][j])continue;
			for(int k=i;k<=rx;k++)
				for(int p=j+1;p<=ry;p++)
					if(f[k][p]&&ck(k-p+j,p+k-i)&&ck(i-p+j,j+k-i))
						ans++;
		}
	write(ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

4
131 603
131 1828
1919 1828
1919 603

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

3
131 603
131 1828
1919 603

output:


result:


Subtask #3:

score: 15
Accepted

Test #11:

score: 15
Accepted
time: 1ms
memory: 7752kb

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: 1ms
memory: 7736kb

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: 1ms
memory: 7724kb

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: 7812kb

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: 1ms
memory: 7620kb

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: 1ms
memory: 7712kb

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: 2981ms
memory: 8176kb

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: 2039ms
memory: 9968kb

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: 3329ms
memory: 8180kb

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: 3179ms
memory: 8344kb

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: 2914ms
memory: 8300kb

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: 0
Time Limit Exceeded

Dependency #4:

100%
Accepted

Test #22:

score: 0
Time Limit Exceeded

input:

5
257 800
766 800
800 353
667 0
42 0

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%