제출 #1134102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134102		alexdd	Wish (LMIO19_noras)	C++20	0 / 100	0 ms	320 KiB

noras

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
int n,r;
vector<pair<int,int>> timp;
map<int,int> mp,nrm;
int mars[1000005];
signed main()
{
    cin>>n>>r;
    int a,b,c,d;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c>>d;
        vector<ld> v(4);
        v[0] = (ld)(r-a-b)/(ld)(c+d-a-b);
        v[1] = (ld)(r-a+b)/(ld)(c+b-a-d);
        v[2] = (ld)(r+a-b)/(ld)(a+d-c-b);
        v[3] = (ld)(r+a+b)/(ld)(a+b-c-d);
        vector<ld> aux;
        for(ld t:v)
        {
            if(abs((ld)a + (ld)(c-a)*t) + abs((ld)b + (ld)(d-b)*t) == r)
            {
                aux.push_back(t);
            }
        }
        if((int)aux.size()==1)
            aux.push_back(aux[0]);
        if(!aux.empty())
        {
            if(aux[0]>aux[1])
                swap(aux[0],aux[1]);
            aux[0] = max(aux[0], (ld)0);
            timp.push_back({ceil(aux[0]), floor(aux[1])});
            if(timp.back().first > timp.back().second)
                timp.pop_back();
        }
    }
    for(auto [x,y]:timp)
    {
        mp[x]++;
        mp[y]++;
    }
    int cate=0;
    for(auto it:mp)
        if(it.second)
            nrm[it.first]=++cate;
    for(int i=0;i<timp.size();i++)
    {
        mars[nrm[timp[i].first]]++;
        mars[nrm[timp[i].second]+1]--;
    }
    int mxm=0;
    for(int i=1;i<=cate;i++)
    {
        mars[i]+=mars[i-1];
        mxm = max(mxm, mars[i]);
    }
    cout<<mxm;
    return 0;
}
/**


a + (c-a)*t
b + (d-b)*t


a + (c-a)*t + b + (d-b)*t = r
t = (r-a-b)/(c+d-a-b)

a + (c-a)*t - b - (d-b)*t = r
t = (r-a+b)/(c+b-a-d)

-a - (c-a)*t + b + (d-b)*t = r
t = (r+a-b)/(a+d-c-b)

-a - (c-a)*t - b - (d-b)*t = r
t = (r+a+b)/(a+b-c-d)


*/

• Subtask 1: 0 / 23
• Subtask 2: 0 / 23
• Subtask 3: 0 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7