QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401193#5155. Faster Than Lightucup-team1716#WA 0ms3592kbC++206.8kb2024-04-28 06:28:302024-04-28 06:28:32

Judging History

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

  • [2024-04-28 06:28:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3592kb
  • [2024-04-28 06:28:30]
  • 提交

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>> &param)
{
    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>> &param)
{
    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'