哪里出错了?
  • 板块P1299 切孔机
  • 楼主HuaJi_360
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/8/21 21:00
  • 上次更新2023/11/6 19:43:24
查看原帖
哪里出错了?
196522
HuaJi_360楼主2020/8/21 21:00

rt,萌新这边60PTS,求救

#include<bits/stdc++.h>
#define reg register int
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
        if(ch=='-'){f=-1;}
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    char F[200];
    int tmp=x>0?x:-x;
    if(tmp==0){putchar('0');return;}
    if(x<0){putchar('-');}
    int cnt=0 ;
    while(tmp>0){
        F[cnt++]=tmp%10+'0';
        tmp/=10;
    }
    while(cnt>0){putchar(F[--cnt]);}
}
struct point{
    int x,y,num;
    point() {}
	point(int a,int b):x(a),y(b) {}
}a[205];
bool cmpx(point a,point b){
    return a.x<b.x;
}
bool cmpy(point a,point b){
    return a.y<b.y;
}
bool cmp(point a,point b){
    if(a.num!=b.num){return a.num<b.num;}
    if(a.x!=b.x){return a.x<b.x;}
    return a.y<b.y;
}
struct paper{
    bool no[5],vis;
}p[505][505];
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
queue<point> q;
int main(){
    memset(p,0,sizeof(p));
	int n=read();
	for(reg i=1;i<=(n<<1);i++){
        a[i].num=(i+1)>>1;
        a[i].x=read(),a[i].y=read();
	}
	reg now=-10000000,u=0;
	sort(a+1,a+(n<<1)+1,cmpx);
	for(reg i=1;i<=(n<<1);i++){
        if(now!=a[i].x){
            now=a[i].x;
            a[i].x=++u;
        }else{a[i].x=u;}
	}
	sort(a+1,a+(n<<1)+1,cmpy);
	now=-10000000,u=0;
	for(reg i=1;i<=(n<<1);i++){
        if(now!=a[i].y){
            now=a[i].y;
            a[i].y=++u;
        }else{a[i].y=u;}
	}
	sort(a+1,a+(n<<1)+1,cmp);
	for(reg i=1;i<=n;i++){
        point p1=a[(i<<1)-1],p2=a[i<<1];
        for(reg j=p1.x+1;j<=p2.x;j++){
            p[j][p1.y].no[3]=true;
            p[j][p1.y+1].no[2]=true;
        }
        for(reg j=p1.y+1;j<=p2.y;j++){
            p[p1.x][j].no[1]=true;
            p[p1.x+1][j].no[0]=true;
        }
	}
	q.push(point(0,0));
	while(q.size()){
        point a=q.front();q.pop();
        for(reg i=0;i<4;i++){
            reg nx=a.x+dx[i],ny=a.y+dy[i];
            if(nx>=220||nx<0||ny>=220||ny<0){continue;}
            if(p[nx][ny].vis||p[a.x][a.y].no[i]){continue;}
            p[nx][ny].vis=true;
            q.push(point(nx,ny));
        }
	}
	reg ans=0;
	for(reg i=0;i<220;i++){
        for(reg j=0;j<220;j++){
            if(p[i][j].vis){continue;}
            ans++;
            p[i][j].vis=true;
            q.push(point(i,j));
            while(q.size()){
                point a=q.front();q.pop();
                for(reg k=0;k<4;k++){
                    reg nx=a.x+dx[k],ny=a.y+dy[k];
                    if(nx>=220||nx<0||ny>=220||ny<0){continue;}
                    if(p[nx][ny].vis){continue;}
                    p[nx][ny].vis=true;
                    q.push(point(nx,ny));
                }
            }
        }
	}
	write(ans);
	return 0;
}

2020/8/21 21:00
加载中...