QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401193 | #5155. Faster Than Light | ucup-team1716# | WA | 0ms | 3592kb | C++20 | 6.8kb | 2024-04-28 06:28:30 | 2024-04-28 06:28:32 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector<pair<ll, ll>> slope_trick_up(vector<pair<ll, ll>> ¶m)
{
sort(param.begin(), param.end());
int n = param.size();
vector<pair<ll, ll>> ret;
for(int i=0; i<n; i++)
{
if(ret.size()==0) ret.pb(param[i]);
else if(ret[ret.size()-1].first == param[i].first)
{
ret.pop_back();
ret.pb(param[i]);
}
else if(ret.size()==1) ret.pb(param[i]);
else
{
int k = ret.size();
while( k > 2 &&
(ret[k-2].second - param[i].second) * (ret[k-1].first - ret[k-2].first) >=
(ret[k-2].second - ret[k-1].second) * (param[i].first - ret[k-2].first)
)
{
ret.pop_back();
k--;
}
ret.pb(param[i]);
}
}
return ret;
}
vector<pair<ll, ll>> slope_trick_down(vector<pair<ll, ll>> ¶m)
{
sort(param.begin(), param.end(), greater<pair<ll, ll>>());
int n = param.size();
vector<pair<ll, ll>> ret;
for(int i=0; i<n; i++)
{
if(ret.size()==0) ret.pb(param[i]);
else if(ret[ret.size()-1].first == param[i].first)
{
ret.pop_back();
ret.pb(param[i]);
}
else if(ret.size()==1) ret.pb(param[i]);
else
{
int k = ret.size();
while( k > 2 &&
(ret[k-2].second - param[i].second) * (ret[k-1].first - ret[k-2].first) >=
(ret[k-2].second - ret[k-1].second) * (param[i].first - ret[k-2].first)
)
{
ret.pop_back();
k--;
}
ret.pb(param[i]);
}
}
return ret;
}
int main()
{
/*ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);*/
int t = 1;
//cin >> t;
while(t-->0)
{
int n;
cin >> n;
vector<ll> x1(n), y1(n), x2(n), y2(n);
for(int i=0; i<n; i++) cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
vector<pair<ll, ll>> coord(n);
for(int i=0; i<n; i++)
{
coord[i].first = y1[i];
coord[i].second = x1[i];
}
vector<pair<ll, ll>> Mpos = slope_trick_up(coord);
for(int i=0; i<n; i++)
{
coord[i].first = y2[i];
coord[i].second = x2[i];
}
vector<pair<ll, ll>> mpos = slope_trick_down(coord);
for(int i=0; i<n; i++)
{
coord[i].first = y2[i];
coord[i].second = x1[i];
}
vector<pair<ll, ll>> Mneg = slope_trick_up(coord);
for(int i=0; i<n; i++)
{
coord[i].first = y1[i];
coord[i].second = x2[i];
}
vector<pair<ll, ll>> mneg = slope_trick_down(coord);
/*for(pair<ll, ll> p: Mpos) cout << p.first << " " << p.second << "\n";
cout << "\n";
for(pair<ll, ll> p: mpos) cout << p.first << " " << p.second << "\n";
cout << "\n";
for(pair<ll, ll> p: Mneg) cout << p.first << " " << p.second << "\n";
cout << "\n";
for(pair<ll, ll> p: mneg) cout << p.first << " " << p.second << "\n";
cout << "\n";*/
bool ans = false;
ll my = 1e9, My = 0;
for(int i=0; i<n; i++)
{
My = max(My, y1[i]);
my = min(my, y2[i]);
}
if(My <= my) ans = true;
int index1 = 0, index2 = 0;
double b = 0;
while(!ans)
{
//cout << "! " << b << "\n";
while(index1 != Mpos.size() - 1 &&
Mpos[index1].first * b + Mpos[index1].second <=
Mpos[index1+1].first * b + Mpos[index1+1].second) index1++;
while(index2 != mpos.size() - 1 &&
mpos[index2].first * b + mpos[index2].second >=
mpos[index2+1].first * b + mpos[index2+1].second) index2++;
//cout << "USE " << index1 << " " << index2 << "\n";
if(Mpos[index1].first * b + Mpos[index1].second <=
mpos[index2].first * b + mpos[index2].second)
{
ans = true;
break;
}
double b1 = 1e18, b2 = 1e18;
if(index1 == Mpos.size() - 1 && index2 == mpos.size() - 1) break;
if(index1 != Mpos.size() - 1)
{
b1 = (double) (Mpos[index1].second - Mpos[index1 + 1].second) /
(Mpos[index1 + 1].first - Mpos[index1].first);
}
if(index2 != mpos.size() - 1)
{
b2 = (double) (mpos[index2].second - mpos[index2 + 1].second) /
(mpos[index2 + 1].first - mpos[index2].first);
}
if(b1 < b2 || index2 == mpos.size() - 1)
{
index1++;
b = b1;
}
else
{
index2++;
b = b2;
}
}
//cout << "\n#####\n\n";
int index3 = Mneg.size() - 1, index4 = mneg.size() - 1;
b = 0;
while(!ans)
{
//cout << "! " << b << "\n";
while(index3 != 0 &&
Mneg[index3].first * b + Mneg[index3].second <=
Mneg[index3-1].first * b + Mneg[index3-1].second) index3--;
while(index4 != 0 &&
mneg[index4].first * b + mneg[index4].second >=
mneg[index4-1].first * b + mneg[index4-1].second) index4--;
//cout << "USE " << index3 << " " << index4 << "\n";
if(Mneg[index3].first * b + Mneg[index3].second <=
mneg[index4].first * b + mneg[index4].second)
{
ans = true;
break;
}
double b1 = -1e18, b2 = -1e18;
if(index3 == 0 && index4 == 0) break;
if(index3 != 0)
{
b1 = (double) (Mneg[index3].second - Mneg[index3 - 1].second) /
(Mneg[index3 - 1].first - Mneg[index3].first);
}
if(index4 != 0)
{
b2 = (double) (mneg[index4].second - mneg[index4 - 1].second) /
(mneg[index4 - 1].first - mneg[index4].first);
}
if(b1 > b2 || index4 == 0)
{
index3--;
b = b1;
}
else
{
index4--;
b = b2;
}
//cout << "!! " << b1 << " " << b2 << "\n";
}
if(ans) cout << "possible";
else cout << "impossible";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
5 1 3 3 4 2 2 4 3 4 1 5 3 5 2 7 3 6 3 8 4
output:
possible
result:
ok single line: 'possible'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 1 1 2 2 1 3 2 4 3 1 4 2 3 3 4 4
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 1 1 2 2 1 3 2 4 3 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3468kb
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999
output:
possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: 'possible'