제출 #128042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128042		yuree5	곡선 자르기 (KOI17_cut)	C++14	35 / 100	1069 ms	26724 KiB

cut

#include <cstdio>

int n;
int vt[1000010];
struct xy{
    int x,y;
};
xy B[1000010];
struct se{
    int s,e;
};
se C[1000010],t[1000010];
void mers(int s,int m,int e){
    int i,p1=s,p2=m+1;
    for(i=s;i<=e;i++){
        if(p1>m||(p2<=e&&C[p1].s>C[p2].s))t[i]=C[p2++];
        else if((p2<=e&&C[p1].s==C[p2].s)){
            if(C[p1].e<C[p2].s)t[i]=C[p2++];
        }
        else t[i]=C[p1++];
    }
    for(i=s;i<=e;i++){
        C[i]=t[i];
    }
}
void msort(int s,int e){
    if(s>=e)return;
    int m=(s+e)/2;
    msort(s,m);
    msort(m+1,e);
    mers(s,m,e);
}
int main(){
    scanf("%d",&n);
    int i,mx=0,my=1000000010,mxi=0;
    for(i=0;i<n;i++){
        scanf("%d %d",&B[i].x,&B[i].y);
        if(B[i].x>mx){
            if(B[i].y<=my){
                mx=B[i].x;
                my=B[i].y;
                mxi=i;
            }
        }else if(B[i].x==mx&&B[i].y<my){
            mx=B[i].x;my=B[i].y;
            mxi=i;
        }
    }
    int s,e,v=0;
    int c=0;
    for(i=mxi;i<n;i++){
        int val=i+1;
        if(val==n)val=0;
        if(B[i].y<0&&B[val].y>0){v=1;s=B[i].x;}
        if(v==1&&B[i].y>0&&B[val].y<0){
            v=0;
            C[c].s=s;
            C[c++].e=B[i].x;
        }
    }
    for(i=0;i<mxi;i++){
        if(B[i].y<0&&B[i+1].y>0){v=1;s=B[i].x;}
        if(v==1&&B[i].y>0&&B[i+1].y<0){
            v=0;
            C[c].s=s;
            C[c++].e=B[i].x;
        }
    }
    for(i=0;i<c;i++){
        if(C[i].e<C[i].s){
            int t=C[i].e;
            C[i].e=C[i].s;
            C[i].s=t;
        }
    }
    msort(0,c-1);
    int j,cnt=0,ccnt=0;
   // printf("\n\n");
    for(i=0;i<c;i++){
        j=i+1;
        bool chk=false;
       // printf("%d :\n",i);
        while(C[i].e>C[j].e&&C[i].s<C[j].s&&j<c){
            //printf("%d %d %d %d\n",C[i].s,C[j].s,C[j].e,C[i].e);
            if(vt[j]==0)cnt++;
            vt[j]=1;
            j++;
            chk=true;
        }
        if(chk==false)ccnt++;
       // printf("\n");
    }
    printf("%d %d",c-cnt,ccnt);
}

컴파일 시 표준 에러 (stderr) 메시지

cut.cpp: In function 'int main()':
cut.cpp:49:11: warning: unused variable 'e' [-Wunused-variable]
     int s,e,v=0;
           ^
cut.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
cut.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&B[i].x,&B[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 0 / 65