| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 44823 |
2018-04-07T10:00:51 Z |
leehosu01 |
None (KOI16_dist) |
C++17 |
|
127 ms |
996 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F(X) (X<0?-1:X>0)
ll T,MT,N,tms,bst=1ll<<62ll;
struct A{
int x,y,dx,dy;void SC(){cin>>x>>y>>dx>>dy;}
ll lcx(){return T*dx+x;}
ll lcy(){return T*dy+y;}
bool operator<(const A&X)const{return T*dx+x==T*X.dx+X.x?T*dy+y>T*X.dy+X.y:T*dx+x<T*X.dx+X.x;}
bool operator==(const A&X)const{return T*dx+x==T*X.dx+X.x&&T*dy+y==T*X.dy+X.y;}
ll Ds(A&X){return (lcx()-X.lcx())*(lcx()-X.lcx())+(lcy()-X.lcy())*(lcy()-X.lcy());}
}S[30001];
int cp(ll*X,ll*Y)
{
ll T=0;
for(int i=0;i<3;i++)
T+=X[i]*Y[i+1]-X[i+1]*Y[i];
return F(T);
}
int ccw(A&x0,A&x1,A&x2)
{
A XA[4]={x0,x1,x2,x0};
ll XX[4],YY[4];
for(int i=0;i<4;i++)
{
XX[i]=XA[i].lcx();
YY[i]=XA[i].lcy();
}
return cp(XX,YY);
}
inline ld slop(A&d1,A&d2)
{
return ((ld)d1.lcy()-d2.lcy())/((ld)d1.lcx()-d2.lcx());
}
bool used[30001];
ll pro(int Ts)
{
list<int>::iterator s1,s2;
list<int>cov;
T=Ts;
sort(S,S+N);
int K=1;
memset(used,0,sizeof(used));
for(int i=0;i>=0;i+=K)
{
if(i==N-1){K=-1,s1=cov.begin(),s2=--cov.end();}
if(i!=0&&used[i])continue;
while(!cov.empty()&&(S[cov.back()]==S[i]||cov.size()>=2&&ccw(S[*(--(--cov.end()))],S[cov.back()],S[i])!=1)){used[cov.back()]=0;cov.pop_back();}
used[i]=1;cov.push_back(i);
}//시작정점은 2번들어간다.
ll MX=0;
list<int>::iterator I=s1,It,J=s2,Jt;
bool mdgd=0;
do{
if(mdgd)
{
if(slop(S[*I],S[*It])<slop(S[*J],S[*Jt]))++I;
else ++J;
}
It=I;++It;
Jt=J;++Jt;
if(It==cov.end())break;
if(Jt==cov.end())break;
MX=max(MX,S[*I].Ds(S[*J]));
MX=max(MX,S[*It].Ds(S[*J]));
if(Jt!=cov.end())
{
MX=max(MX,S[*I].Ds(S[*Jt]));
MX=max(MX,S[*It].Ds(S[*Jt]));
}
mdgd=1;
}while(It!=s2&&Jt!=cov.end());
if(It!=s2)
while(I!=s2){
It=I;++It;
MX=max(MX,S[*I].Ds(S[*J]));
if(Jt!=cov.end())
MX=max(MX,S[*I].Ds(S[*Jt]));
if(It==cov.end())break;
MX=max(MX,S[*It].Ds(S[*J]));
if(Jt!=cov.end())
MX=max(MX,S[*It].Ds(S[*Jt]));
++I;
}
else if(J!=cov.end()&&Jt!=cov.end())
while(J!=cov.end()&&Jt!=cov.end()){
Jt=J;++Jt;
MX=max(MX,S[*I].Ds(S[*J]));
MX=max(MX,S[*It].Ds(S[*J]));
if(Jt==cov.end())break;
MX=max(MX,S[*I].Ds(S[*Jt]));
MX=max(MX,S[*It].Ds(S[*Jt]));
++J;
}
if(MX<bst)bst=MX,tms=Ts;
else if(MX==bst&&tms>Ts)tms=Ts;
return MX;
}
int main()
{
int i;
//freopen("in.txt","r",stdin);
cin>>N>>MT;
for(i=0;i<N;i++)S[i].SC();
ll l=0,r=MT,m,PS[3],minl,minI;
while(l<r)
{
m=l+r>>1;
minl=1ll<<62ll;
minI=-1;
for(i=-1;i<2;i++)
{
if(m+i>=0&&m+i<=MT)
{
PS[i+1]=pro(m+i);
if(PS[i+1]<minl)
{
minl=PS[i+1];
minI=i;
}
}
}
if(minI==-1)r=m-1;
else if(minI==0)r=m;
else l=m+1;
}
cout<<tms<<'\n'<<bst;
}
Compilation message
dist.cpp: In function 'll pro(int)':
dist.cpp:52:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
while(!cov.empty()&&(S[cov.back()]==S[i]||cov.size()>=2&&ccw(S[*(--(--cov.end()))],S[cov.back()],S[i])!=1)){used[cov.back()]=0;cov.pop_back();}
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dist.cpp: In function 'int main()':
dist.cpp:115:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
m=l+r>>1;
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
