Submission #565731

#	Time	Username	Problem	Language	Result	Execution time	Memory
565731		SilentVisitor	Roads (CEOI20_roads)	C++17	100 / 100	252 ms	12128 KiB

roads

/*
     author : SilentVisitor;
     created on 12.01.22 12.52 A.M. 
*/
#include<bits/stdc++.h> 
using namespace std; 
#ifdef _DEBUG 
#include "algo/debug.h" 
#else
#define debug(...) 69420 
#endif
#define deb(...) union 

#define ll long long
#define i64 ll64_t 

#define F first 
#define S second

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define pii pair<int, int> 
#define pll pair<ll, ll> 
#define sz(s) s.size()
vector<char> data = {'a', 'e', 'i', 'o', 'u'}; 
int N, vis[200005];
pll p[100005][2];
pii ans[100005];
vector<pii> v;
struct sort_by_y
{
    double intersect(int a, int x) const
    {
        if (p[a][0].F == p[a][1].F)
            return (p[a][0].S + p[a][1].S) / 2;
        
        return p[a][0].S + double(p[a][1].S - p[a][0].S) * double(x - p[a][0].F) / double(p[a][1].F - p[a][0].F);
    }
    bool operator()(int a, int b) const
    {
        int curx = max(p[a][0].F, p[b][0].F);
        if (p[a][0].F == p[a][1].F)
            curx = p[a][0].F;
        if (p[b][0].F == p[b][1].F)
            curx = p[b][0].F;
        return intersect(a, curx) < intersect(b, curx);
    }
};
map<int, pii, sort_by_y> sweep;
void solve(){
        cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> p[i][0].F >> p[i][0].S >> p[i][1].F >> p[i][1].S;
    for (int i = 1; i <= N; i++)
        if (p[i][0] > p[i][1])
            swap(p[i][0], p[i][1]);
    for (int i = 1; i <= N; i++)
    {
        v.emplace_back(pii{i, 0});
        v.emplace_back(pii{i, 1});
    }
    p[0][0] = pii{-1e8, 1e8}, p[0][1] = pii{1e8, 1e8};
    sort(v.begin(), v.end(), [&](pii p1, pii p2)
         {
                 return p[p1.F][p1.S]/*.F*/ < p[p2.F][p2.S]/*.F*/;
         });
    sweep[0] = {0, 0};
    for (int i = 0; i < v.size(); i++)
    {
        
        if (v[i].S == 1)
        {
            auto iter = sweep.erase(sweep.find(v[i].F));
            sweep[iter->F] = v[i];
        }
        else
        {
            auto iter = sweep.upper_bound(v[i].F);
            ans[v[i].F] = sweep[iter->F];
            sweep[v[i].F] = v[i];
            iter = sweep.upper_bound(v[i].F);
            sweep[iter->F] = v[i];
        }
    }
 
    for (int i = 1; i <= N; i++)
        if(ans[i] != pii{0, 0})
            cout << p[i][0].F << " " << p[i][0].S << " " << p[ans[i].F][ans[i].S].F << " " << p[ans[i].F][ans[i].S].S << "\n";

}
main(void){
       ios::sync_with_stdio(false); 
       cin.tie(0); 
       cout.tie(0); 
       solve(); 
       return 0; 
}

Compilation message (stderr)

roads.cpp: In function 'void solve()':
roads.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
roads.cpp: At global scope:
roads.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(void){
      | ^~~~

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40