Submission #30595

#	Time	Username	Problem	Language	Result	Execution time	Memory
30595		kajebiii	먼 별 (KOI16_dist)	C++14	100 / 100	713 ms	3348 KiB

dist

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 3e4 + 100;

int sign(ll x) {return (x>0) - (x<0);}
struct PT {
	int x, y;
	PT() : x(0), y(y) {}
	PT(int xx, int yy) : x(xx), y(yy) {}
	PT operator-(const PT &o) const {return PT(x-o.x, y-o.y);}
	int ccw(const PT &o) const {return sign(1ll * x * o.y - 1ll * y * o.x);}
	int ccw(const PT &a, const PT &b) const {return (a-*this).ccw(b-*this);}
	bool operator<(const PT &o) const {
		if(y != o.y) return y < o.y;
		return x < o.x;
	}
	bool operator==(const PT &o) const {
		return x == o.x && y == o.y;
	}
	int getL() {return abs(x) + abs(y); }
};

int N, T, Nr[MAX_N][4];
ll getV(int day) {
	vector<PT> Ps;
	for(int i=0; i<N; i++) Ps.push_back(PT(Nr[i][0] + Nr[i][2] * day, Nr[i][1] + Nr[i][3] * day));
	sort(ALL(Ps)); 
	Ps.erase(unique(ALL(Ps)), Ps.end());
	int pN = SZ(Ps);
//	printf("day : %d\n", day); for(int i=0; i<pN; i++) printf("[%d %d] ", Ps[i].x, Ps[i].y); puts("");

	sort(Ps.begin()+1, Ps.end(), [&](PT a, PT b) {
		int cv = Ps[0].ccw(a, b);
		if(cv != 0) return cv == 1;
		return (a-Ps[0]).getL() < (b-Ps[0]).getL();
	});

	vector<PT> Cv;
	for(int i=0; i<pN; i++) {
		while(SZ(Cv) >= 2 && Cv[SZ(Cv)-2].ccw(Cv.back(), Ps[i]) <= 0) Cv.pop_back();
		Cv.push_back(Ps[i]);
	}

	int cN = SZ(Cv);
	ll maxV = 0;
	for(int i=0, j=0; i<cN; i++) {
		if(i == j) j = (j+1) % cN;
		int ni = (i+1) % cN, nj = (j+1) % cN;
		while((Cv[ni]-Cv[i]).ccw(Cv[nj]-Cv[j]) > 0) nj = (nj+1) % cN, j = (j+1) % cN;
		PT diff = Cv[i] - Cv[j];
		maxV = max(maxV, 1ll*diff.x*diff.x + 1ll*diff.y*diff.y);
	}
	return maxV;
}

int ans = -1; ll minD = LINF;
void push(int ix, ll val) {
//	printf("%d is %lld\n", ix, val);
	if(minD > val || (minD == val && ans > ix) ) minD = val, ans = ix;
}
int main() {
	cin >> N >> T;
	for(int i=0; i<N; i++) for(int j=0; j<4; j++) scanf("%d", &Nr[i][j]);

	for(int l=0, r=T; l<=r; ) {
		if(r - l <= 5) {
			for(int i=l; i<=r; i++) push(i, getV(i));
			break;
		}
		int m0 = (l+l+r) / 3, m1 = (l+r+r) / 3;
		ll v0 = getV(m0), v1 = getV(m1);
		if(v0 <= v1) r = m1 - 1, push(m1, v1); else l = m0 + 1, push(m0, v0);
	}
	printf("%d\n%lld\n", ans, minD);
	return 0;
}

Compilation message (stderr)

dist.cpp: In constructor 'PT::PT()':
dist.cpp:23:2: warning: 'PT::y' is initialized with itself [-Winit-self]
  PT() : x(0), y(y) {}
  ^
dist.cpp: In function 'int main()':
dist.cpp:78:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) for(int j=0; j<4; j++) scanf("%d", &Nr[i][j]);
                                                                      ^

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