제출 #151218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151218		ChoKang	먼 별 (KOI16_dist)	C++14	2 / 100	96 ms	3796 KiB

dist

#include <bits/stdc++.h>
#define MAX_N 30100
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct point{
	ll x, y, dx, dy;
	point(ll x = 0, ll y = 0, ll dx = 0, ll dy = 0): x(x), y(y), dx(dx), dy(dy) {}
};

int n, t;
vector<point> p, e, hull;

int ccw(point a, point b, point c){
	ll val = (b.x-a.x) * (c.y-b.y) - (b.y-a.y) * (c.x-b.x);
	if(val > 0) return 1;
	if(val < 0) return -1;
	return val;
}
bool comp(point p1, point p2){
	int val = ccw(e[0], p1, p2);
	if(val > 0) return true;
	if(val < 0) return false;
	if(p1.x != p2.x) return p1.x < p2.x;
	return p1.y < p2.y;
}
void graham_scan(){
	int Size = 0;
	for(int i = 0; i < n; i++){
		while(Size >= 2 && ccw(hull[Size-2], hull[Size-1], e[i]) <= 0){ Size--; hull.pop_back(); }
		hull.eb(e[i]);
	}
}

ull rotating(int T){

	int pivot = 0;
	for(int i = 0; i < n; i++){
		e.eb(p[i].x + T*p[i].dx, p[i].y + T*p[i].dy, 0, 0);
		if(e[pivot].x > e[i].x || (e[pivot].x == e[i].x && e[pivot].y > e[i].y)) pivot = i;
	}
	
	swap(e[0], e[pivot]);
	sort(e.begin()+1, e.end(), comp);
	graham_scan();

	int Size = hull.size(), ni, nj, j = 1;
	point a, b, c;
	ull ret = 0;

	for(int i = 0; i < Size; i++){
		ni = (i+1)%Size;
		while(1){
			nj = (j+1)%Size;
			a = { 0, 0, 0, 0 };
			b={ hull[ni].x-hull[i].x, hull[ni].y-hull[i].y, 0, 0 };
            c={ hull[nj].x-hull[j].x, hull[nj].y-hull[j].y, 0, 0 };
            int k = ccw(a, b, c);
            if(k > 0) j = nj;
            else break;
		}
		ull val = (ull)((hull[i].x - hull[j].x) * (hull[i].x - hull[j].x))
		 			+ (ull)((hull[i].y - hull[j].y) * (hull[i].y - hull[j].y));
		ret = max(ret, val);
	}
	e.clear();
	hull.clear();
	return ret;
}

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

	cin >> n >> t;

	for(ll i = 0, x1, y1, dx1, dy1; i < n; i++){
		cin >> x1 >> y1 >> dx1 >> dy1;
		p.eb(x1, y1, dx1, dy1);
	}

	int S = 0, E = t;
	ull ans = ULLONG_MAX, ind = 0;

	while(S < E-3){
		int f1 = (2*S + E)/3, f2 = (S + 2*E)/3;
		ull val1 = rotating(f1), val2 = rotating(f2);
		if(val1 > val2) S = f1 + 1;
		else if(val1 < val2) E = f2 - 1;
		else E = f2 -1;
	}
	for(int i = S; i <= E; i++){
		ull val = rotating(i);
		if(val < ans){ ind = i; ans = val; }
	}
	cout << ind << endl << ans <<endl;

	return 0;
}

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