oj.uz

Submission #197010

# Submission time Handle Problem Language Result Execution time Memory
197010 2020-01-18T06:14:22 Z dennisstar None (KOI16_dist) C++11
0 / 100
 2000 ms 2272 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
#define fastio ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int N, T;
ll x[30010], y[30010], dx[30010], dy[30010];

pll operator -(pll p1, pll p2) { return pll(p1.fi-p2.fi, p1.se-p2.se); }

int ccw(pll v1, pll v2) {
	if (v1.fi*v2.se-v1.se*v2.fi > 0) return 1; //ccw
	else if (v1.fi*v2.se-v1.se*v2.fi < 0) return -1; //cw
	else return 0; //collinear
}
int ccw1(pll p1, pll p2, pll p3) { return ccw(p2-p1, p3-p1); }
int ccw2(pll p1, pll p2, pll p3, pll p4) { return ccw(p2-p1, p4-p3); }
ll sq(int k) { return k*k; }

vector<pll> make_ch(vector<pll> &P) { //convex hull
	sort(all(P)); unq(P);
	vector<pll> ch;
	for (auto &i:P) {
		while (ch.size()>1 && ccw1(ch[ch.size()-2], ch.back(), i)!=1) ch.pop_back();
		ch.eb(i);
	}
	reverse(all(P)); int tp=ch.size();
	for (auto &i:P) {
		while (tp<ch.size() && ccw1(ch[ch.size()-2], ch.back(), i)!=1) ch.pop_back();
		ch.eb(i);
	}
	ch.pop_back();
	return ch;
}

ll dist(vector<pll> &P) {
	P=make_ch(P); ll ret=0;
	for (int i=0, j=1; i<P.size(); i++) {
		while (ccw2(P[i], P[(i+1)%P.size()], P[j], P[(j+1)%P.size()])==1) j=(j+1)%P.size();
		ret=max(ret, sq(P[i].fi-P[j].fi)+sq(P[i].se-P[j].se));
	}
	return ret;
}

ll solve(int t) {
	vector<pll> P;
	for (int i=1; i<=N; i++) P.eb(x[i]+dx[i]*t, y[i]+dy[i]*t);
	return dist(P);
}

int main() {
	scanf("%d %d", &N, &T);
	for (int i=1; i<=N; i++) scanf("%lld %lld %lld %lld", &x[i], &y[i], &dx[i], &dy[i]);
	vector<pll> p;
	int s=0, e=T, mi=0; ll ans=(1ll<<60);
	while (s<e) {
		int m1=(s*2+e)/3, m2=(s+e*2+1)/3;
		ll r1=solve(m1), r2=solve(m2);
		if (r1>r2) s=m1+1;
		else if (r1<r2) e=m2-1;
	}
	printf("%d\n%lld\n", s, solve(s));
	return 0;
}

Compilation message

dist.cpp: In function 'std::vector<std::pair<long long int, long long int> > make_ch(std::vector<std::pair<long long int, long long int> >&)':
dist.cpp:39:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (tp<ch.size() && ccw1(ch[ch.size()-2], ch.back(), i)!=1) ch.pop_back();
          ~~^~~~~~~~~~
dist.cpp: In function 'll dist(std::vector<std::pair<long long int, long long int> >&)':
dist.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0, j=1; i<P.size(); i++) {
                     ~^~~~~~~~~
dist.cpp: In function 'int main()':
dist.cpp:65:16: warning: unused variable 'mi' [-Wunused-variable]
  int s=0, e=T, mi=0; ll ans=(1ll<<60);
                ^~
dist.cpp:65:25: warning: unused variable 'ans' [-Wunused-variable]
  int s=0, e=T, mi=0; ll ans=(1ll<<60);
                         ^~~
dist.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &T);
  ~~~~~^~~~~~~~~~~~~~~~~
dist.cpp:63:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%lld %lld %lld %lld", &x[i], &y[i], &dx[i], &dy[i]);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -