Submission #31206

#	Time	Username	Problem	Language	Result	Execution time	Memory
31206		leejseo	먼 별 (KOI16_dist)	C++98	100 / 100	303 ms	2924 KiB

dist

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
 
using namespace std;
 
typedef struct {
  int x, y, dx, dy;
} star;
 
#define MAX_T 10000000
#define MAX_N 30000
 
star L[MAX_N];
 
int n, T;
 
long long int dist(star &a, star &b, int t){
  long long int a_x = a.x + t*a.dx;
  long long int a_y = a.y + t*a.dy;
  long long int b_x = b.x + t*b.dx;
  long long int b_y = b.y + t*b.dy;
  return (a_x - b_x)*(a_x - b_x) + (a_y - b_y) * (a_y - b_y);
}
/* 
long long int g(int t){
  long long cnt = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<i; j++){
      long long temp = dist(L[i], L[j], t);
      if (temp > cnt){
        cnt = temp;
      }
    }
  }
  return cnt;
}
*/

struct compare_with_time
{ 
  compare_with_time(int t) { m_t = t; } // only if you really need the object state
  int m_t;

  bool operator()(const star &a, const star &b) const 
  { 
    if ((a.x + m_t * a.dx) < (b.x + m_t * b.dx)) return true;
    if (((a.x + m_t * a.dx) == (b.x + m_t * b.dx))&& ((a.y + m_t * a.dy) < (b.y + m_t * b.dy))) return true;
    return false;
  }
};
/*
star items[MAX_STAR];
int item_count;
int t;

sort(item, item + item_count, compare_with_time(t))

int compare(star a, star b){
  if (a.x > b.x) return 1;
  else if (a.x == b.x){
    if (a.y > b.y) return 1;
    if (a.y < b.y) return -1;
    return 0;
  }
  return -1;
}
*/

int CCW(const star &P, const star &P1, const star &P2, int t){
  long long x1 = P.x + P.dx * t;
  long long x2 = P1.x + P1.dx * t;
  long long x3 = P2.x + P2.dx * t;
  long long y1 = P.y + P.dy * t;
  long long y2 = P1.y + P1.dy * t;
  long long y3 = P2.y + P2.dy * t;
  long long Area = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
  if (Area == 0) return 0;
  if (Area > 0) return 1;
  return -1;
}

long long dist(const star &a, const star &b, int t){
  long long delta_x = (a.x + t * a.dx) - (b.x + t*b.dx);
  long long delta_y = (a.y + t * a.dy) - (b.y + t*b.dy);
  return delta_x * delta_x + delta_y * delta_y;
}

bool temp_f(vector<star> &U, vector<star> &L , int i, int j, int t){
  long long a1, a2, a3, a4;
  a1 = (U[i+1].y + U[i+1].dy * t) - (U[i].y + U[i].dy * t);
  a2 = (L[j].x + L[j].dx * t) - (L[j-1].x + L[j-1].dx * t);
  a3 = (L[j].y + L[j].dy * t) - (L[j-1].y + L[j-1].dy * t);
  a4 = (U[i+1].x + U[i+1].dx * t) - (U[i].x + U[i].dx * t);
  return (a1 * a2) > (a3 * a4);
}

long long g(int t){
  sort(L, L+n, compare_with_time(t));
  vector<star> UP, LO;
  int u=0, l=0;
  for (int i=0; i<n; i++){
    star q = L[i];
    while ((u > 1) && (CCW(UP[u-2], UP[u-1], q, t) >= 0)){
      UP.pop_back();
      u = u-1;
    }
    while ((l > 1) && (CCW(LO[l-2], LO[l-1], q, t) <= 0)){
      LO.pop_back();
      l = l-1;
    }
    UP.push_back(q);
    u++;
    LO.push_back(q);
    l++;
  }
  int i = 0;
  int j = l-1;
  long long DIST = 0;
  while ((i < u-1) || (j > 0)){
    long long cnt = dist(UP[i], LO[j], t);
    if (cnt > DIST) DIST = cnt;
    if (i == u-1) j--;
    else if (j == 0) i++;
    else if (temp_f(UP, LO, i, j, t)) i++;
    else j--;
  }
  long long cnt = dist(UP[i], LO[j], t);
  if (cnt > DIST) DIST = cnt;
  return DIST;
}

int f(){
  int lo = 0;
  int hi = T;
  while (lo <= hi){
    int llh = (2*lo + hi)/3;
    int lhh = (lo + 2*hi + 1)/3;
    if (g(llh) <= g(lhh)) hi = lhh - 1;
    else lo = llh+1;
  }
  return lo;
}
 
int main(){
  scanf("%d%d", &n, &T);
  for (int i=0; i<n; i++){
    scanf("%d%d%d%d", &(L[i].x), &(L[i].y), &(L[i].dx), &(L[i].dy));
  }
  int day = f();
  long long d = g(day);
  printf("%d\n", day);
  printf("%lld\n", d);
  return 0;
}

Compilation message (stderr)

dist.cpp: In function 'int main()':
dist.cpp:147:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &T);
                        ^
dist.cpp:149:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &(L[i].x), &(L[i].y), &(L[i].dx), &(L[i].dy));
                                                                    ^

• Subtask 1: 2 / 2
• Subtask 2: 40 / 40
• Subtask 3: 39 / 39
• Subtask 4: 19 / 19