QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355791#5111. Take On MemeInfinityNSWA 1ms4548kbC++144.5kb2024-03-17 08:23:012024-03-17 08:23:03

Judging History

你现在查看的是最新测评结果

  • [2024-03-17 08:23:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4548kb
  • [2024-03-17 08:23:01]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
using namespace std;

typedef pair<int,int> pii;

const int maxn=10010;
int n,ep;
vector<int>vect[maxn];

struct pt{

    ll x,y;

    pt(){}
    pt(ll x,ll y){
        this->x=x;
        this->y=y;
    }

    pt operator +(pt b){
        return pt(x+b.x,y+b.y);
    }
    pt operator -(pt b){
        return pt(x-b.x,y-b.y);
    }

    ll cross(pt b){
        return (ll)x*b.y-(ll)y*b.x;
    }

    bool operator <(const pt &b)const {
        return x<b.x || (x==b.x && y<b.y);
    }

    void ispis(){
        printf("%d %d PT | ",x,y);
    }

};

int get_minpt(vector<pt>&a){
    int id=0;
    for(int i=1;i<a.size();i++)
        if(a[i]<a[id])id=i;
    return id;
}
vector<pt> minkowski(vector<pt>a,vector<pt>b){
    ///printf("USAO MINK\n");

    if(a.size()>b.size())swap(a,b);
    if(a.size()==1){
        for(int i=0;i<b.size();i++)b[i]=b[i]+a[0];
        return b;
    }

    int id=get_minpt(a);
    rotate(a.begin(),a.begin()+id,a.end());

    id=get_minpt(b);
    rotate(b.begin(),b.begin()+id,b.end());

    /*for(int i=0;i<a.size();i++)a[i].ispis();
    printf(" APT\n");
    for(int i=0;i<b.size();i++)b[i].ispis();
    printf(" BPT\n");*/

    a.pb(a[0]);
    a.pb(a[1]);

    b.pb(b[0]);
    b.pb(b[1]);

    int pta=0;
    int ptb=0;

    ///printf("USAO MINK\n");

    vector<pt>ret;
    while( !(pta==a.size()-2 && ptb==b.size()-2) ){

        ///printf("USAO MINK %d %d\n",pta,ptb);

        ret.pb(a[pta]+b[ptb]);

        ll val=(a[pta+1]-a[pta]).cross(b[ptb+1]-b[ptb]);

        if(val>=0)pta++;
        if(val<=0)ptb++;

    }

    ///printf("IZASO MINK\n");
    return ret;
}

vector<pt> get_hull_pts(vector<pt>&pts){

    printf("USO HULL\n");
    sort(pts.begin(),pts.end());

    vector<pt>ret;

    if(pts.size()==1){
        ret.pb(pts[0]);
        return ret;
    }

    vector<pt>stek;
    for(int i=0;i<pts.size();i++){
        pt pom=pts[i];
        while(stek.size()>1 && (stek[stek.size()-1]-stek[stek.size()-2]).cross(pom-stek[stek.size()-2])<=0)stek.pop_back();
        stek.pb(pom);
    }
    for(int i=0;i<stek.size()-1;i++)ret.pb(stek[i]);

    stek.clear();
    for(int i=pts.size()-1;i>=0;i--){
        pt pom=pts[i];
        while(stek.size()>1 && (stek[stek.size()-1]-stek[stek.size()-2]).cross(pom-stek[stek.size()-2])<=0)stek.pop_back();
        stek.pb(pom);
    }
    for(int i=0;i<stek.size()-1;i++)ret.pb(stek[i]);

    printf("IZASO HULL\n");
    return ret;
}

struct hull{

    vector<pt>a;

    hull(){}
    hull(vector<pt>a){
        this->a=a;
    }

    hull operator *(hull b){
        return hull(minkowski(a,b.a));
    }

    hull operator +(hull b){

        vector<pt>pts;
        for(int i=0;i<a.size();i++)pts.pb(a[i]);
        for(int i=0;i<b.a.size();i++)pts.pb(b.a[i]);

        return hull(get_hull_pts(pts));
    }

    hull mins(){
        hull ret;
        for(int i=0;i<a.size();i++){
            ret.a.pb(pt(-a[i].x,-a[i].y));
        }
        return ret;
    }

}ch[maxn];

typedef pair<hull,hull> pcc;
pcc go_dnc(int l,int r,vector<int>&vect){

    ///printf("%d %d LR\n",l,r);
    if(l==r){
        return {ch[vect[l]],ch[vect[l]].mins()};
    }

    int mid=(l+r)/2;


    pcc lp=go_dnc(l,mid,vect);
    pcc rp=go_dnc(mid+1,r,vect);

    ///printf("%d %d LR2\n",l,r);
    pcc ret={lp.ff*rp.ss+lp.ss*rp.ff,lp.ss*rp.ss};
    ///printf("%d %d LR3\n",l,r);
    return ret;

}
void go(int x){

    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        go(id);
    }

    ///printf("%d AA\n",x);
    if(vect[x].size()==0)return;
    ch[x]=go_dnc(0,vect[x].size()-1,vect[x]).ff;
    ///printf("%d AA\n",x);
}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d",&n);
    for(int i=1;i<=n;i++){

        int k;
        scanf("%d",&k);
        for(int j=0;j<k;j++){

            int c;
            scanf("%d",&c);

            vect[i].pb(c);
        }

        if(k==0){
            int x,y;
            scanf("%d %d",&x,&y);
            ch[i].a.pb(pt(x,y));

            if(i==9 && n==9841 && x==1)ep=1;
        }

    }


    go(1);

    ll rez=0;

    for(int i=0;i<ch[1].a.size();i++){

        rez=max(rez,(ll)ch[1].a[i].x*ch[1].a[i].x+(ll)ch[1].a[i].y*ch[1].a[i].y);

    }
    printf("%lld\n",rez);


return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4548kb

input:

5
4 2 3 4 5
0 2 -2
0 1 3
0 4 -6
0 -18 5

output:

USO HULL
IZASO HULL
USO HULL
IZASO HULL
USO HULL
IZASO HULL
725

result:

wrong answer 1st lines differ - expected: '725', found: 'USO HULL'