QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376149#8505. Almost Alignedinstallb#Compile Error//C++206.3kb2024-04-03 21:50:232024-04-03 21:50:23

Judging History

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

  • [2024-04-03 21:50:23]
  • 评测
  • [2024-04-03 21:50:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db eps = 1e-12;
const db pi = acos(-1.0);
const db MX = 4e9;

const int N = 2000005;

int sgn(db x){
    if(x > -eps && x < eps) return 0;
    if(x > 0) return 1;
    return -1;
}

struct point{
    db x,y;
    point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {}
    bool operator < (const point &p) const{
        if(sgn(x - p.x) == 0) return sgn(y - p.y) < 0;
        return x < p.x;
    }
};
point operator - (const point &p1,const point &p2){
    return point(p1.x - p2.x,p1.y - p2.y);
}
point operator + (const point &p1,const point &p2){
    return point(p1.x + p2.x,p1.y + p2.y);
}
point operator * (db x,const point &p){
    return point(x * p.x,x * p.y);
}

db dot(point p1,point p2){
    return p1.x * p2.x + p1.y * p2.y;
}

db det(point p1,point p2){
    return p1.x * p2.y - p2.x * p1.y;
}

struct line{
    point a,b;
    line () : a(), b() {}
    line (point _a,point _b) : a(_a), b(_b) {}
};

point sec_point(line x,line y){
    point ret,va,vb,vu;
    va = x.b - x.a; vb = y.b - y.a; vu = y.b - x.b;
    ret = x.b + (det(vu,vb) / det(va,vb)) * va;
    return ret;
}

bool cmp_hp(line x,line y){
    db a1 = atan2(x.b.y - x.a.y,x.b.x - x.a.x);
    db a2 = atan2(y.b.y - y.a.y,y.b.x - y.a.x);
    if(sgn(a1 - a2) == 0) return sgn(det(y.a - x.a,y.b - x.a)) > 0;
    return a1 < a2;
}

bool equ_hp(line x,line y){
    db a1 = atan2(x.b.y - x.a.y,x.b.x - x.a.x);
    db a2 = atan2(y.b.y - y.a.y,y.b.x - y.a.x);
    return sgn(a1 - a2) == 0;
}

line q[N];
void half_plane(line *s,int n,point *t,int &r){
    int l = 1; r = 0;
    sort(s + 1,s + 1 + n,cmp_hp);
    for(int i = 1;i <= n;i ++){
        if(i > 1 && equ_hp(s[i],s[i - 1])) continue;
        while(r - l > 0 && sgn(det(s[i].b - t[r],s[i].a - t[r])) > 0) r --;
        while(r - l > 0 && sgn(det(s[i].b - t[l + 1],s[i].a - t[l + 1])) > 0) l ++;
        q[++ r] = s[i];
        if(r - l > 0){
            t[r] = sec_point(q[r - 1],q[r]);
        }
    }
    while(r - l > 0 && sgn(det(q[l].b - t[r],q[l].a - t[r])) > 0) r --;
    t[r + 1] = sec_point(q[l],q[r]);r ++;
    for(int i = 1;i <= r - l;i ++) t[i] = t[i + l];
    r = r - l;
} // left side

int n;
db x[N],y[N],vx[N],vy[N];
line li[N];
int m; point qs[N];

vector <pair <point,db> > H[2][2];
vector <db> ti;
void calct(int id,int xy){
    vector <point> G;
    db pos0,posmx,posmi;

    if(!id){
        li[n + 1] = line(point(4e9,4e18),point(-4e9,4e18));
        li[n + 2] = line(point(0,4e18),point(0,-4e18));
        li[n + 3] = line(point(MX,-4e18),point(MX,4e18));
        half_plane(li,n + 3,qs,m);
        pos0 = posmx = -1e99;
        for(int i = 1;i <= n;i ++){
            pos0 = max(pos0,xy ? y[i] : x[i]);
            posmx = max(posmx,xy ? y[i] + MX * vy[i] : x[i] + MX * vx[i]);
        }
        for(int i = 1;i <= m;i ++) cout << "QS" << qs[i].x << ',' << qs[i].y << " \n"[i == m];
        G.push_back(point(0,pos0));
        for(int i = 1;i <= m;i ++) if(qs[i].y < 3e18) G.push_back(qs[i]);
        G.push_back(point(MX,posmx));
    }
    else{
        li[n + 1] = line(point(-4e9,-4e18),point(4e9,-4e18));
        li[n + 2] = line(point(0,4e18),point(0,-4e18));
        li[n + 3] = line(point(MX,-4e18),point(MX,4e18));
        half_plane(li,n + 3,qs,m);
        pos0 = posmi = 1e99;
        for(int i = 1;i <= n;i ++){
            pos0 = min(pos0,xy ? y[i] : x[i]);
            posmi = min(posmi,xy ? y[i] + MX * vy[i] : x[i] + MX * vx[i]);
        }
        G.push_back(point(0,pos0));
        for(int i = m;i >= 1;i --) if(qs[i].y > -3e18) G.push_back(qs[i]);
        G.push_back(point(MX,posmi));
    }
    for(int i = 0;i + 1 < G.size();i ++){
        if(sgn(G[i + 1].x - G[i].x) != 0){
            db ver = (G[i + 1].y - G[i].y) / (G[i + 1].x - G[i].x);
            H[id][xy].push_back({G[i],ver});
            ti.push_back(G[i].x);
        }
    }
}

void solve(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++){
        scanf("%lf %lf %lf %lf",&x[i],&y[i],&vx[i],&vy[i]);
    }
    for(int i = 1;i <= n;i ++) li[i] = line(point(0,x[i]),point(MX,x[i] + MX * vx[i]));
    calct(0,0);
    for(int i = 1;i <= n;i ++) li[i] = line(point(MX,x[i] + MX * vx[i]),point(0,x[i]));
    calct(1,0);
    for(int i = 1;i <= n;i ++) li[i] = line(point(0,y[i]),point(MX,y[i] + MX * vy[i]));
    calct(0,1);
    for(int i = 1;i <= n;i ++) li[i] = line(point(MX,y[i] + MX * vy[i]),point(0,y[i]));
    calct(1,1);

    sort(ti.begin(),ti.end());
    db ans = 1e99;
    for(int i = 0;i + 1 < ti.size();i ++){
        db l = ti[i],r = ti[i + 1];
        for(auto [p,v] : H[0][0]) cout << l << ' ' << p.x << ',' << p.y << ' ' << v << endl;
        cout << H[0][0].size() << ',' << (upper_bound(H[0][0].begin(),H[0][0].end(),make_pair(point(l,1e99),0.0)) == H[0][0].begin()) << endl;
        auto [xup,xuv] = *(-- upper_bound(H[0][0].begin(),H[0][0].end(),make_pair(point(l,1e99),0.0)));
        for(auto [p,v] : H[1][0]) cout << l << ' ' << p.x << ',' << p.y << ' ' << v << endl;
        auto [xdp,xdv] = *(-- upper_bound(H[1][0].begin(),H[1][0].end(),make_pair(point(l,1e99),0.0)));
        for(auto [p,v] : H[0][1]) cout << l << ' ' << p.x << ',' << p.y << ' ' << v << endl;
        auto [yup,yuv] = *(-- upper_bound(H[0][1].begin(),H[0][1].end(),make_pair(point(l,1e99),0.0)));
        for(auto [p,v] : H[1][1]) cout << l << ' ' << p.x << ',' << p.y << ' ' << v << endl;
        auto [ydp,ydv] = *(-- upper_bound(H[1][1].begin(),H[1][1].end(),make_pair(point(l,1e99),0.0)));
        db xdel = xuv - xdv,ydel = yuv - ydv;
        db xlen = ((l - xup.x) * xuv + xup.y) - ((l - xdp.x) * xdv + xdp.y);
        db ylen = ((l - yup.x) * yuv + yup.y) - ((l - ydp.x) * ydv + ydp.y);
        cout << l << ' ' << xlen << ' ' << ylen << ' ' << xdel << ' ' << ydel << '\n';
        for(int ti = 1;ti <= 100;ti ++){
            db midl = (l + l + r) / 3.0;
            db midr = (l + r + r) / 3.0;
            db calcl = fabs(xlen + xdel * midl) * fabs(ylen + ydel * midl);
            db calcr = fabs(xlen + xdel * midr) * fabs(ylen + ydel * midr);
            ans = min(ans,min(calcl,calcr));
            if(calcl < calcr) r = midr;
            else l = midl;
        }
    }
    cout << fixed << setprecision(15) << ans << '\n';
}

int main(){
    solve();
    return 0;
}as

Details

answer.code:184:2: error: ‘as’ does not name a type
  184 | }as
      |  ^~
answer.code: In function ‘void solve()’:
answer.code:138:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  138 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
answer.code:140:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |         scanf("%lf %lf %lf %lf",&x[i],&y[i],&vx[i],&vy[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~