oj.uz

Submission #58789

# Submission time Handle Problem Language Result Execution time Memory
58789 2018-07-19T12:09:56 Z andy627 None (KOI16_dist) C++17
2 / 100
 123 ms 2948 KB 
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define LL long long
#define INF 9e18
using namespace std;

struct xyv{
    LL x,y,dx,dy,t;
}star[33333];

struct xyt{
    LL x,y;
    double t;

    bool operator<(const xyt A)const{
        if(t!=A.t) return t<A.t;
        if(y!=A.y) return y<A.y;
        return x<A.x;
    }
}ver[33333];

LL n,t;
vector<int> con;

LL ccw(int i,int j,int k){
    return (star[i].x*star[j].y+star[j].x*star[k].y+star[k].x*star[i].y)
    -(star[j].x*star[i].y+star[k].x*star[j].y+star[i].x*star[k].y);
}

void convex_hull(int day){
    int mnp=1;

    for(int i=1;i<=n;i++){
        ver[i].x=star[i].x+day*star[i].dx;
        ver[i].y=star[i].y+day*star[i].dy;

        if(ver[mnp].y>ver[i].y) mnp=i;
        if(ver[mnp].y==ver[i].y && ver[mnp].x>ver[i].x) mnp=i;
    }
    for(int i=1;i<=n;i++) ver[i].t=atan2(ver[i].y-ver[mnp].y,ver[i].x-ver[mnp].x);

    sort(ver+1,ver+n+1);

    con.clear();
    con.push_back(1);
    con.push_back(2);
    for(int i=3;i<=n;i++){
        int idx1=con.size()-2;
        int idx2=con.size()-1;

        while(idx1>=0 && ccw(con[idx1],con[idx2],i)<=0){
            con.pop_back();
            idx1=con.size()-2;
            idx2=con.size()-1;
        }
        con.push_back(i);
    }
}

LL dist(int i,int j){
    return (ver[con[i]].x-ver[con[j]].x)*(ver[con[i]].x-ver[con[j]].x)
    +(ver[con[i]].y-ver[con[j]].y)*(ver[con[i]].y-ver[con[j]].y);
}

LL rotating_calipers(){
    int siz=con.size();

    LL ans=0;
    for(int i=0,j=0;i<siz;i++){
        while(dist(i,j)<dist(i,(j+1)%siz)) j=(j+1)%siz;
        ans=max(ans,dist(i,j));
    }

    return ans;
}

LL solve(int day){
    convex_hull(day);
    //printf("#%d",con.size());
    return rotating_calipers();
}

int main(){
    //freopen("input4.txt","r",stdin);

    scanf("%lld %lld",&n,&t);
    for(int i=1;i<=n;i++) scanf("%lld %lld %lld %lld",&star[i].x,&star[i].y,&star[i].dx,&star[i].dy);

    int s=0,e=t,m1,m2;
    while(e-s>2){
        m1=(s+s+e)/3; m2=(s+e+e)/3;
        //printf("%d %d %d %d",s,m1,m2,e);

        LL res1=solve(m1);
        //printf("!");
        LL res2=solve(m2);
        //printf("!\n");

        if(res1<=res2) e=m2;
        else s=m1;
    }

    int ans_day=0;
    LL ans_dist=INF,res;
    for(int i=s;i<=e;i++){
        res=solve(i);
        if(ans_dist>res){
            ans_day=i;
            ans_dist=res;
        }
    }

    printf("%d\n%lld\n",ans_day,ans_dist);

    return 0;
}

Compilation message

dist.cpp: In function 'int main()':
dist.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&n,&t);
     ~~~~~^~~~~~~~~~~~~~~~~~~
dist.cpp:89: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",&star[i].x,&star[i].y,&star[i].dx,&star[i].dy);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 3 ms 516 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 628 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 2948 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 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 3 ms 516 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Incorrect 19 ms 820 KB Output isn't correct
12 Halted 0 ms 0 KB -