17nm2 곡선 자르기
질의 응답 코너입니다.
2018.07.17 23:10:45
#include <stdio.h>
#include <algorithm>
int arr[500002], a, n, num, cnt, count=0x7fffffff, sol1, sol2;
struct w
{
int a;
int b;
} ne[500002];
bool cmp(w x, w y)
{
return x.a<y.a;
}
bool safe(int a, int b)
{
return (a<0 && b>0) || (a>0 && b<0);
}
void low()
{
for(int i=cnt; i<num; i++)
ne[i-cnt]= {arr[i], 0};
for(int i=0; i<cnt; i++)
ne[i+num-cnt]= {arr[i], 0};
}
int main()
{
scanf("%d", &n);
for(int i=0; i<n/2; i++)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if(safe(y1, y2) || y1==y2)
{
arr[num]=x1;
if(x1<count)
{
cnt=num;
count=x1;
}
num++;
}
}
low();
for(int i=0; i<num; i+=2)
{
if(ne[i].a<ne[i+1].a)
{
ne[i].b=1;
ne[i+1].b=-1;
}
else
{
ne[i].b=-1;
ne[i+1].b=1;
}
}
std::sort(ne, ne+num, cmp);
count=0;
for(int i=0; i<num; i++)
{
count+=ne[i].b;
if(count==0) sol1++;
}
for(int i=0; i<num-1; i++)
{
if(ne[i].b==1 && ne[i+1].b==-1) sol2++;
}
printf("%d %d", sol1, sol2);
}
이렇게 썼는데 왜 테스트 케이스 24번에서 이상하게 나올까요...
