| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 57754 |
2018-07-16T02:11:29 Z |
gs18081 |
None (KOI16_dist) |
C++11 |
|
229 ms |
2124 KB |
/*
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct star{
ll xx,yy,dx,dy;
}input[30010];
ll n,maxday,top;
struct nowstar{
ll x, y;
}now[30010],st[30010];
ll cross(ll a, ll b, ll c, ll d){return a*d-b*c;}
bool ccmp(nowstar A, nowstar B)
{
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
bool rcmp(nowstar A, nowstar B)
{
if(cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)==0)
{
if (A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
return cross(A.x-now[1].x,A.y-now[1].y,B.x-now[1].x,B.y-now[1].y)>0;
}
ll dist(nowstar A, nowstar B){return (B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y);}
ll maxdis(ll day)
{
ll i,j,ret=0,top=0;
for(i=1;i<=n;i++)
{
now[i].x=input[i].xx+input[i].dx*day;
now[i].y=input[i].yy+input[i].dy*day;
}
sort(now+1,now+n+1,ccmp);
sort(now+2,now+n+1,rcmp);
st[top++]=now[1];
st[top++]=now[2];
for(i=3;i<=n;i++)
{
if(now[i].x==now[i-1].x&&now[i].y==now[i-1].y) continue;
while(top>=2&&cross(st[top-1].x-st[top-2].x,st[top-1].y-st[top-2].y,now[i].x-st[top-1].x,now[i].y-st[top-1].y)<=0) top--;
st[top++]=now[i];
}
for(i=0,j=0;i<top;i++)
{
if(i==j) j=(j+1)%top;
int ni=(i+1)%top,nj=(j+1)%top;
while(cross(st[ni].x-st[i].x,st[ni].y-st[i].y,st[nj].x-st[j].x,st[nj].y-st[j].y)>0){nj=(nj+1)%top,j=(j+1)%top;}
ret=max(ret,dist(st[i],st[j]));
}
return ret;
}
int main()
{
ll i;
scanf("%lld %lld",&n, &maxday);
for(i=1;i<=n;i++)
{
scanf("%lld %lld %lld %lld", &input[i].xx, &input[i].yy, &input[i].dx, &input[i].dy);
}
ll l=0, r=maxday, x1, x2,ci=50;
while(ci--&&l+1<r)
{
x1=((ll)2*l+r)/3;
x2=((ll)2*r+l)/3;
if(maxdis(x1)>maxdis(x2)) l=x1;
else r=x2;
}
ll ans1=maxdis(l),ans2=l;
for(i=l+1;i<=r;i++)
{
if(maxdis(i)<ans1)
{
ans1=maxdis(i);
ans2=i;
}
}
printf("%lld\n%lld", ans2,ans1);
}
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
struct star{
ll x,y,dx,dy;
};
int N,T;
star stars[40000];
ll myabs(ll num){
return num>0?num:-num;
}
ll delta(pi a,pi b,pi c){
/*return a.first*b.second - a.second * b.first
+b.first * c.second - b.second * c.first
+c.first * a.second - c.second * a.first;
*/
return (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first);
}
ll dist(pi a,pi b){
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
ll absdist(pi a,pi b){
return myabs(a.first-b.first)+myabs(a.second-b.second);
}
vector<pi> dots;
vector<pi> hull;
ll maxdist(int day){
dots.clear();
for(int i=0;i<N;i++){
dots.push_back(pi(stars[i].x+day*stars[i].dx,stars[i].y+stars[i].dy*day));
}
sort(dots.begin(),dots.end(),[&](pi a,pi b){
return a.second==b.second?a.first<b.first:a.second<b.second;
});
dots.erase(unique(dots.begin(),dots.end()),dots.end());
sort(dots.begin()+1,dots.end(),[&](pi a,pi b){
if(delta(dots[0],a,b)==0){
if(a.first==b.first) return a.second<b.second;
return a.first<b.first;
}
return delta(dots[0],a,b)<0;
//return delta(dots[0],a,b)==0?absdist(dots[0],a)<absdist(dots[0],b) : delta(dots[0],a,b)>0;
});
hull.clear();
hull.push_back(dots[0]);
for(int i=1;i<dots.size();i++){
while(hull.size()>=2&&delta(hull[hull.size()-2],hull.back(),dots[i])<=0) hull.pop_back();
hull.push_back(dots[i]);
}
ll ret=0;
int j=1%hull.size();
for(int i=0;i<hull.size();i++){
int ni=(i+1)%hull.size();
for(;;){
int nj=(j+1)%hull.size();
if(delta(pi(0,0),pi(hull[ni].first-hull[i].first,hull[ni].second-hull[i].second),pi(hull[nj].first-hull[j].first,hull[nj].second-hull[j].second))<=0)
break;
j=nj;
}
ret=max(ret,dist(hull[i],hull[j]));
}
return ret;
}
int main(){
scanf("%d %d",&N,&T);
for(int i=0;i<N;i++){
scanf("%lld %lld %lld %lld",&stars[i].x,&stars[i].y,&stars[i].dx,&stars[i].dy);
}
int s=0;
int e=T;
ll ans=maxdist(0);
int day=0,x1,x2;
while(s+5<e){
x1=((ll)2*s+e)/3;
x2=((ll)2*e+s)/3;
if(maxdist(x1)>maxdist(x2)) s=x1;
else e=x2;
}
if(e<s) swap(s,e);
//*/
if(T<=20){
s=0;
e=T;
}
//*/
ans=maxdist(s);
day=s;
for(int i=s+1;i<=e;i++){
if(ans>maxdist(i)){
day=i;
ans=maxdist(i);
}
}
printf("%d\n%lld\n",day,ans);
return 0;
}
Compilation message
dist.cpp: In function 'll maxdist(int)':
dist.cpp:136:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<dots.size();i++){
~^~~~~~~~~~~~
dist.cpp:142:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<hull.size();i++){
~^~~~~~~~~~~~
dist.cpp: In function 'int main()':
dist.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&T);
~~~~~^~~~~~~~~~~~~~~
dist.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld %lld",&stars[i].x,&stars[i].y,&stars[i].dx,&stars[i].dy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
5 ms |
588 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
588 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
5 ms |
588 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
588 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Incorrect |
16 ms |
644 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
2124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
5 ms |
588 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
588 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Incorrect |
16 ms |
644 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
