(25051) 천체 관측

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

단계별로 풀어보기

51단계(기하 3) 7번째

 

 

 

모든 점을 360도 기준으로 반시계 방향으로 정렬하는데, 지금까지 쓰던 정렬 함수는 180도 기준에서만 통하는 방식이므로 위쪽인지 아래쪽인지 먼저 판단한 뒤 같은 쪽에 있을 때만 외적으로 각도를 정렬한다.

어떤 점 (x,y)에 대해 (y,-x)는 이 점을 시계 방향으로 90도 돌린 점이다. 망원경의 왼쪽 끝 범위가 (x,y)의 별을 볼 수 있게 돌렸다면, 원점에서 (y,-x)로 반직선을 그었을 때 반직선 오른쪽에 있는 별은 망원경의 범위를 벗어난다. 범위 내 별들에 대해 망원경의 가격에 따라 볼 수 있는 아름다움의 총합을 구하고 최대값을 갱신하면 된다.

볼 수 있는 범위는 원형이므로 정답이 되는 망원경 범위가 1사분면과 4사분면에 걸쳐있는 경우가 있을 수 있으므로 정렬이 끝난 뒤 1사분면에 있는 별을 맨 뒤에 덧붙인다.

 

 

 

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

struct Star{
  long x;
  long y;
  long w;
  
  Star vert(){
    Star res;
    res.x= y;
    res.y= -x;
    return res;
  }
  
  int upside() const {
    return (y>0 || (y==0&&x>0));
  }
  
  bool operator <(const Star &A) const {
    if(upside()!=A.upside())  return upside()>A.upside();
    if(y*A.x!=x*A.y)  return y*A.x<x*A.y;
    return x*x+y*y<A.x*A.x+A.y*A.y;
  }
};

int ccw(Star p2, Star p3){
  long t= p2.x*p3.y-p3.x*p2.y;
  
  if(t>0)  return 1;
  else if(t<0)  return -1;
  else  return 0;
}

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

  int n, m;
  
  cin >> n >> m;
  
  vector<Star> v(n);
  vector<long> p(m), tot(m);
  
  for(int i=0;i<n;i++)  cin >> v[i].x >> v[i].y >> v[i].w;
  for(int i=0;i<m;i++)  cin >> p[i];
  
  sort(v.begin(), v.end());
  sort(p.begin(), p.end(), greater<long> ());
  
  for(int i=0;i<n&&v[i].x>=0&&v[i].y>=0;i++)  v.push_back(v[i]);
  
  int s= 0, e= 0;
  long ans= -p[m-1];
  for(;e<v.size();e++){
    while(s<e && ccw(v[e].vert(), v[s])<0){
      long dist= v[s].x*v[s].x+v[s].y*v[s].y;
      
      for(int i=0;i<m&&dist<=p[i];i++)  tot[i]-= v[s].w;
      
      s++;
    }
    
    long dist= v[e].x*v[e].x+v[e].y*v[e].y;
    
    for(int i=0;i<m&&dist<=p[i];i++){
      tot[i]+= v[e].w;
      
      ans= max(ans, tot[i]-p[i]);
    }
  }
  
  cout << ans;

  return 0;
}