(10254) 고속도로

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

단계별로 풀어보기

51단계(기하 3) 2번째

 

 

 

단순히 두 점의 쌍을 전부 비교하면 O(N^2)로 시간 초과가 난다. 컨벡스 헐 알고리즘을 사용한 뒤 볼록다각형을 이루는 점들에 대해 회전하는 캘리퍼스 알고리즘을 이용하면 O(V)에 가장 먼 두 점을 찾을 수 있다.

 

 

 

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

struct Point{
  long x, y;
  long p, q;
  Point(int x1= 0, int y1= 0): x(x1), y(y1), p(1), q(0) {}
  
  void set(const Point &base){
    p= x-base.x;
    q= y-base.y;
  }

  bool operator <(const Point &A) const {
    if(q*A.p!=p*A.q)  return q*A.p<p*A.q;
    if(p*p+q*q!=A.p*A.p+A.q*A.q)  return p*p+q*q<A.p*A.p+A.q*A.q;
    if(y!=A.y)  return y<A.y;
    return x<A.x;
  }
  
  Point operator -(const Point &A){
    Point ret;
    ret.x= x-A.x;
    ret.y= y-A.y;
    ret.p= p-A.p;
    ret.q= q-A.q;
    return ret;
  }

  Point operator +(const Point &A){
    Point ret;
    ret.x= x+A.x;
    ret.y= y+A.y;
    ret.p= p+A.p;
    ret.q= q+A.q;
    return ret;
  }
};

inline int ccw(const Point &p1, const Point & p2, const Point & p3){
  long res= 1L*(p2.x-p1.x)*(p3.y-p1.y)-1L*(p3.x-p1.x)*(p2.y-p1.y);
  
  if(res>0)  return 1;
  else if(res<0)  return -1;
  else  return 0;
}

void solve(){
  int n;

  cin >> n;

  vector<Point> p(n);
  
  for(int i=0;i<n;i++){
    cin >> p[i].x >> p[i].y;
  }

  sort(p.begin(), p.end());
  for(int i=1;i<n;i++)  p[i].set(p[0]);
  sort(p.begin()+1, p.end());

  stack<int> s;
  s.push(0);  s.push(1);
  
  for(int i=2;i<n;i++){
    while(s.size()>=2){
      int second= s.top();
      s.pop();
      int first= s.top();
        
      if(ccw(p[first],p[second],p[i])>0){
        s.push(second);
        
        break;
      }
    }

    s.push(i);
  }
  
  int sz= s.size();
  vector<int> v;
  v.reserve(sz);
  
  while(!s.empty()){
    v.push_back(s.top());
    s.pop();
  }
  
  int max1, max2, p1= 0, p2= 1;
  long maxval= 0;
  
  for(int i=0;i<2*sz;i++){
    int dx= p[v[p1]].x-p[v[p2]].x;
    int dy= p[v[p1]].y-p[v[p2]].y;
    long dist= 1L*dx*dx+1L*dy*dy;
    
    if(maxval<dist){
      maxval= dist;
      max1= v[p1];
      max2= v[p2];
    }
    
    int a= ccw(p[v[p1]], p[v[(p1+1)%sz]], p[v[(p2+1)%sz]]-p[v[p2]]+p[v[(p1+1)%sz]]);
    
    if(a>0){
      p1= (p1+1)%sz;
    }
    else  p2= (p2+1)%sz;
  }
  
  cout << p[max1].x << " " << p[max1].y << " " << p[max2].x << " " << p[max2].y << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  
  cin >> T;
  
  while(T--){
    solve();
  }

  return 0;
}