QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#389301#8505. Almost AlignedRobeZHWA 614ms97272kbC++232.4kb2024-04-14 09:07:432024-04-14 09:07:43

Judging History

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

  • [2024-04-14 09:07:43]
  • 评测
  • 测评结果:WA
  • 用时:614ms
  • 内存:97272kb
  • [2024-04-14 09:07:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
struct P{
    ll x,y;
    P operator+(P p){return {x+p.x,y+p.y};}
    P operator-(P p){return {x-p.x,y-p.y};}
    ll operator*(P p){return x*p.y-y*p.x;}
    bool operator<(P p){
        if(x!=p.x)return x<p.x;
        return y<p.y;
    }
    bool operator==(P p){return x==p.x&&y==p.y;}
};
struct STA{
    void init(){
        sort(all(a));
        int ptr=0;
        for(int i=0;i<a.size();++i){
            while(ptr>1&&(a[ptr-1]-a[ptr-2])*(a[i]-a[ptr-1])>=0)--ptr;
            a[ptr++]=a[i];
        }
        a.resize(ptr);
        reverse(all(a));
    }
    long double next(){
        assert(a.size()>1);
        P tmp=a[a.size()-1]-a[a.size()-2];
        return -1.L*tmp.y/tmp.x;
    }
    long double val(long double t){
        return a.back().x*t+a.back().y;
    }
    vector<P>a;
};
const long double eps=1e-10,inf=8e18;
int sgn(long double x){return x<-eps?-1:x>eps;}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;cin>>n;
    vector<P>x(n),y(n);
    for(int i=0;i<n;++i){
        cin>>x[i].y>>y[i].y>>x[i].x>>y[i].x;
    }
    array<STA,4>s;
    s[0].a=x;
    for(P&p:x)p=P{0,0}-p;
    s[1].a=x;
    s[2].a=y;
    for(P&p:y)p=P{0,0}-p;
    s[3].a=y;
    for(int i=0;i<4;++i)s[i].init();
    long double ans=inf;
    bool fg=0;
    for(;;) {
        int ptr = -1;
        long double tim;
        for (int i = 0; i < 4; ++i)
            if (s[i].a.size() > 1 && (ptr == -1 || s[i].next() < tim)) {
                tim = s[i].next();
                ptr = i;
            }
        if (ptr == -1)break;
//        cerr << tim << endl;
        if (sgn(tim) >= 0) {
            long double xdif = (s[0].val(tim) + s[1].val(tim));
            long double ydif = (s[2].val(tim) + s[3].val(tim));
//            cerr << xdif << " " << ydif << endl;
            fg = 1;
            ans = min(ans, xdif * ydif);
        }
        s[ptr].a.pop_back();
    }
    // final calc
    if(fg==0){
        ans=(s[0].a[0].y+s[1].a[0].y)*(s[2].a[0].y+s[3].a[0].y);
    }
    if(s[0].a[0]+s[1].a[0]==P{0,0}||s[2].a[0]+s[3].a[0]==P{0,0})
        ans=0;
    cout<<fixed<<setprecision(15)<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.222222222222222

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4064kb

input:

3
0 -1 0 2
1 1 1 1
-1 1 -1 1

output:

0.000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1

output:

4.000000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

1
0 0 0 0

output:

0.000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

3999984000031.999951601028442

result:

ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'

Test #6:

score: -100
Wrong Answer
time: 614ms
memory: 97272kb

input:

1000000
-871226 486657 -467526 31395
-65837 846554 469710 -907814
927993 -45099 713462 -276539
261942 483255 746021 811070
63449 -779486 588838 -413687
812070 -87868 -813499 -420768
112521 -622607 -832012 921368
-182120 517379 -401743 -837524
-685985 337832 643014 135144
12895 326935 -495720 930620
...

output:

0.000000000000000

result:

wrong answer 1st numbers differ - expected: '3999996000000.0000000', found: '0.0000000', error = '1.0000000'