oj.uz

답안 #30594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30594 2017-07-25T08:25:59 Z kajebiii 먼 별 (KOI16_dist) C++14
2 / 100
 119 ms 3084 KB 
#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 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) {
			printf("hello\n");
			return true;
		}
		return cv == 1;
	});

	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

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:80: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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2492 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2492 KB Output is correct
5 Correct 0 ms 2492 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 0 ms 2492 KB Output is correct
9 Correct 0 ms 2492 KB Output is correct
10 Correct 0 ms 2492 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2492 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2492 KB Output is correct
5 Correct 0 ms 2492 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 0 ms 2492 KB Output is correct
9 Correct 0 ms 2492 KB Output is correct
10 Correct 0 ms 2492 KB Output is correct
11 Correct 13 ms 2492 KB Output is correct
12 Correct 13 ms 2492 KB Output is correct
13 Correct 13 ms 2492 KB Output is correct
14 Incorrect 13 ms 2492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 3080 KB Output is correct
2 Correct 103 ms 3080 KB Output is correct
3 Incorrect 109 ms 3084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2492 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2492 KB Output is correct
5 Correct 0 ms 2492 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 0 ms 2492 KB Output is correct
9 Correct 0 ms 2492 KB Output is correct
10 Correct 0 ms 2492 KB Output is correct
11 Correct 13 ms 2492 KB Output is correct
12 Correct 13 ms 2492 KB Output is correct
13 Correct 13 ms 2492 KB Output is correct
14 Incorrect 13 ms 2492 KB Output isn't correct
15 Halted 0 ms 0 KB -