이 문제는 왜 플레에 있는지 모르겠을 정도로 간단한데, 그냥 선분교차에 대한 처리 방법만 알면 된다.
선분이 교차한다는 것은 한 선분을 기준으로, 나머지 선분의 두 점이 각각 다른 방향에 존재하는 것이다.
여기서 방향은 전에 풀었던 convex-hull 에서 배웠던 ccw 함수를 쓰면 된다.
그런데 방향이 달라도 직선이 아니라 선분이기 때문에 교차하지 않을 수 있다.
따라서 한 선분만 기준으로 검사하는 것이 아니라, 각 선분을 기준으로 삼아서 검사를 두번 진행해야 한다.
그리고 한가지 경우를 더 처리해야 하는데, 두 선분의 점 4개가 모두 일직선에 있을 경우이다.
이 때는 한 선분의 max 꼭짓점이 다른 선분의 min꼭짓점보다 크기만 하면 교차한다.
이렇게 교차 여부 검사 함수만 짜면, 나머지는 그냥 이중for문을 돌면서 교차하면 union-find로 그룹지어주면 끝이다.
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int parent[3004];
int groups[3004];
struct Data
{
pair<int,int> a,b;
}line[3004];
int ccw(pair<int,int>a, pair<int,int>b, pair<int,int>c)
{
pair<int,int>ab = make_pair(b.first-a.first,b.second-a.second);
pair<int,int>ac = make_pair(c.first-a.first,c.second-a.second);
if(ab.first*ac.second - ab.second*ac.first>0) return 1;
else if(ab.first*ac.second - ab.second*ac.first<0) return -1;
else return 0;
}
bool check(pair<int,int>a, pair<int,int>b, pair<int,int>c, pair<int,int>d)
{
if(ccw(a,b,c)*ccw(a,b,d)==0 && ccw(c,d,a)*ccw(c,d,b)==0)
{
if(max(a,b)>=min(c,d) && min(a,b)<=max(c,d)) return true;
else return false;
}
if(ccw(a,b,c)*ccw(a,b,d)<=0 && ccw(c,d,a)*ccw(c,d,b)<=0) return true;
else return false;
}
int finds(int a)
{
if(a==parent[a]) return a;
return parent[a] = finds(parent[a]);
}
void unions(int a, int b)
{
if(finds(a)!=finds(b))
{
parent[finds(a)] = finds(b);
}
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
line[i]={make_pair(a,b),make_pair(c,d)};
}
for(int i=1;i<=N;i++) parent[i]=i;
for(int i=1;i<N;i++)
{
for(int j=i+1;j<=N;j++)
{
if(check(line[i].a,line[i].b,line[j].a,line[j].b))
{
unions(i,j);
}
}
}
for(int i=1;i<=N;i++)
{
groups[finds(i)]++;
}
int groupnum=0,maxgroup=0;
for(int i=1;i<=N;i++)
{
if(groups[i]!=0)
{
groupnum++;
if(maxgroup<groups[i]) maxgroup = groups[i];
}
}
printf("%d\n%d",groupnum,maxgroup);
}구현 코드이다.
