oj.uz

Submission #151217

# Submission time Handle Problem Language Result Execution time Memory
151217 2019-09-02T08:52:40 Z ChoKang None (KOI16_dist) C++14
2 / 100
 127 ms 4592 KB 
#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){
		int f1 = S +(E-S)/3, f2 = E -(E-S)/3;
		ull val1 = rotating(f1), val2 = rotating(f2);
		if(val1 > val2) S = f1+1;
		else E = f2-1;
	}
	/*for(int i = S; i <= E; i++){
		ull val = rotating(i);
		if(val < ans){ ind = i; ans = val; }
	}*/
	cout << S << endl << rotating(S) <<endl;

	return 0;
}

Compilation message

dist.cpp: In function 'int main()':
dist.cpp:85:6: warning: unused variable 'ans' [-Wunused-variable]
  ull ans = ULLONG_MAX, ind = 0;
      ^~~
dist.cpp:85:24: warning: unused variable 'ind' [-Wunused-variable]
  ull ans = ULLONG_MAX, ind = 0;
                        ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 19 ms 664 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 4592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 19 ms 664 KB Output isn't correct
12 Halted 0 ms 0 KB -