QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#389301 | #8505. Almost Aligned | RobeZH | WA | 614ms | 97272kb | C++23 | 2.4kb | 2024-04-14 09:07:43 | 2024-04-14 09:07:43 |
Judging History
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'