(2162) 선분 그룹

https://www.acmicpc.net/problem/2162

단계별로 풀어보기

39단계(기하 2) 7번째

 

 

 

N의 범위가 3000이므로 O(N^2)으로 모든 선분 쌍에 대해 선분 교차를 판정해도 충분하다.

선분 교차를 판정하는 알고리즘에 크기를 저장하는 유니온 파인드를 결합하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

struct Cord{
  long x;
  long y;
  
  Cord(): x(0), y(0) {}
  Cord(long x0, long y0): x(x0), y(y0) {}
  
  bool operator <(const Cord& other) const{
    return make_pair(x,y)<make_pair(other.x,other.y);
  }
  bool operator <=(const Cord& other) const{
    return make_pair(x,y)<=make_pair(other.x,other.y);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<Cord, Cord>> v(n+1);
  vector<pair<int, int>> uf(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i].first.x >> v[i].first.y >> v[i].second.x >> v[i].second.y;
  
  for(int i=1;i<=n;i++)  uf[i]= {i, 1};
  
  auto find= [&](auto self, int x) -> pair<int, int> {
    if(uf[x].first==x)  return uf[x];
    else  return uf[x]= self(self, uf[x].first);
  };
  
  auto merge= [&](int x, int y){
    auto xres= find(find, x);
    auto yres= find(find, y);
    
    if(xres.first==yres.first)  return;
    
    uf[xres.first].second+= uf[yres.first].second;
    uf[yres.first].first= xres.first;
  };
  
  auto ccw= [](Cord &p1, Cord &p2, Cord &p3){
    long t= (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
    
    if(t>0)  return 1;
    else if(t<0)  return -1;
    else  return 0;
  };
  
  auto iscross= [&ccw](Cord &p1, Cord &p2, Cord &p3, Cord &p4){
    long a= ccw(p1,p2,p3)*ccw(p1,p2,p4);
    long b= ccw(p4,p3,p1)*ccw(p4,p3,p2);
    
    if(a==0 && b==0){
      return (min(p1,p2)<=max(p3,p4) && min(p3,p4)<=max(p1,p2));
    }else if(a<=0&&b<=0){
      return true;
    }else{
      return false;
    }
  };
  
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      if(iscross(v[i].first, v[i].second, v[j].first, v[j].second)){
        merge(i, j);
      }
    }
  }
  
  int cnt= 0, maxval= 0;
  
  for(int i=1;i<=n;i++){
    if(find(find, i).first==i){
      cnt++;
      maxval= max(maxval, find(find, i).second);
    }
  }
  
  cout << cnt << "\n" << maxval;
  
  return 0;
}