QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165226#4952. Cutting with Lasersacm202226010311RE 1ms5928kbC++142.1kb2023-09-05 16:49:532023-09-05 16:49:54

Judging History

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

  • [2023-09-05 16:49:54]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5928kb
  • [2023-09-05 16:49:53]
  • 提交

answer

#include <iostream>
#include <iomanip>
#include <cmath>
#include <queue>
#include <set>
int d[2010][2010];
int st[2010][2010];
int dx[4]={0,0,2,-2};
int dy[4]={2,-2,0,0};
struct pos
{
	int  x;
	int  y;
	bool operator<(pos b)const
	{
		if(x==b.x)return y<b.y;
		return x<b.x;
	}
};
int a,b;
int res;
using namespace std;
void dfs()
{
	pos now={a,b};
	//cout<<"a"<<a<<"b"<<b<<endl;
	queue<pos> qq;
	qq.push(now);
	st[b][a]=1;
	while(qq.size())
	{
		pos now=qq.front();
		int aa=now.x;
		int bb=now.y;
		qq.pop();
		//cout<<aa<<" "<<bb<<endl;
		res++;
		d[bb][aa]=res+2;
		for(int i=0;i<4;i++)
		{
			if(!d[bb+dy[i]/2][aa+dx[i]/2]&&!st[bb+dy[i]][aa+dx[i]])
			{
				st[bb+dy[i]][aa+dx[i]]=1;
				pos tmp={aa+dx[i],bb+dy[i]};
				qq.push(tmp);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	int arr[n][2];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i][0]>>arr[i][1];
		arr[i][0]*=2;
		arr[i][1]*=2;
	}
	a=arr[0][0]+1;
	b=arr[0][1]+1;
	int sx=arr[0][0];
	int sy=arr[0][1];
	//cout<<a<<" "<<b<<endl;
	for(int i=1;i<n;i++)
	{
		if(arr[i][0]==arr[i-1][0])//当x相同的时候 
		{
			int t=arr[i][0];
			int r=max(arr[i][1],arr[i-1][1]);
			int l=min(arr[i][1],arr[i-1][1]);
			for(int a=l;a<=r;a++)
			d[a][t]=1;
		}
		else//当y相等的时候 
		{
			int t=arr[i][1];
			int r=max(arr[i][0],arr[i-1][0]);
			int l=min(arr[i][0],arr[i-1][0]);
			for(int a=l;a<=r;a++)
			d[t][a]=1; 
		}
	}
	if(arr[n-1][0]==arr[0][0])//当x相等的时候 
	{
		int t=arr[n-1][0];
		int l=min(arr[n-1][1],arr[0][1]);
		int r=max(arr[n-1][1],arr[0][1]);
		for(int a=l;a<=r;a++)
		d[a][t]=1; 
	}
	else 
	{
		int t=arr[0][1];
		int l=min(arr[n-1][0],arr[0][0]);
		int r=max(arr[n-1][0],arr[0][0]);
		for(int a=l;a<=r;a++)
		d[t][a]==1;
	}
	if(d[sy+1][sx])b=sy+1;
	else b=sy-1;
	if(d[sy][sx+1])a=sx+1;
	else a=sx-1;
	//cout<<a<<" "<<b<<endl;
	/*for(int i=20;i>=0;i--)
	{
		for(int j=0;j<=20;j++)
		cout<<d[i][j]<<" ";
		cout<<endl;
	}*/
	dfs();
	/*for(int i=20;i>=0;i--)
	{
		for(int j=0;j<=20;j++)
		cout<<d[i][j]<<" ";
		cout<<endl;
	}*/
	cout<<res;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5928kb

input:

8
2 1
7 1
7 4
3 4
3 2
5 2
5 6
2 6
2 1

output:

17

result:

ok single line: '17'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5696kb

input:

14
1 1
8 1
8 6
6 6
6 2
2 2
2 4
7 4
7 5
3 5
3 3
4 3
4 6
1 6
1 1

output:

21

result:

ok single line: '21'

Test #3:

score: -100
Runtime Error

input:

4
1 1
1 1000
1000 1000
1000 1
1 1

output:


result: