oj.uz

Submission #290084

# Submission time Handle Problem Language Result Execution time Memory
290084 2020-09-03T11:52:43 Z model_code Roads (CEOI20_roads) C++17
100 / 100
 425 ms 13776 KB 
#include <bits/stdc++.h>
#define   maxN  100001

using namespace std;
struct Point{
   long long   x,y;
   Point(long long a, long long b){x=a; y=b;}
   Point(){};
};
struct Segment{
  Point a, b;
  Segment(){};
  Segment(Point aa, Point bb){a=aa; b=bb;}
};

Segment S[maxN];
pair<int,bool> AB[2*maxN];
Point Rmost[maxN];
vector<Segment> Sol;
int n;

int Turn(Point A, Point B, Point C){
   long long Kereszt=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
   if (Kereszt <0)
      return -1;
   else if (Kereszt >0)
      return 1;
   else
      return  0;
}
struct SegOrd{
  bool operator() (const int& u, const int& v) const{
    int tua=Turn(S[u].a,S[u].b,S[v].a);
    int tub=Turn(S[u].a,S[u].b,S[v].b);
    int tva=Turn(S[v].a,S[v].b,S[u].a);
    int tvb=Turn(S[v].a,S[v].b,S[u].b);
    return  tua>0 && tub>0 || tva<0 && tvb<0 ||
            tua==0 && tub==0&& tva==0 && tvb==0 && S[u].a.y<S[v].a.y;
  }
};

set<int, SegOrd> Sline;

bool ABord(pair<int,bool> a, pair<int,bool> b){
  Point ap,bp;
  if(a.second) ap=S[a.first].a; else ap=S[a.first].b;
  if(b.second) bp=S[b.first].a; else bp=S[b.first].b;
  if(ap.x<bp.x) return true;
  if(ap.x>bp.x) return false;
  return (ap.y<bp.y);
}

void ReadIn(){
  int x1,y1,x2,y2;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>x1>>y1>>x2>>y2;
    if(x1<x2 || x1==x2 && y1<y2)
      S[i]={{x1,y1},{x2,y2}};
    else
      S[i]={{x2,y2},{x1,y1}};
  }
}

int main(){
  ReadIn();
  for(int i=0;i<n;i++){
    AB[i]={i,true};
    AB[i+n]={i,false};
  }
  sort(AB, AB+2*n, ABord);
  long long maxxy=10000000;
  Segment sentinel={{-maxxy,-maxxy},{maxxy, -maxxy}};
  S[n]=sentinel;   Sline.insert(n);
  int s0=AB[0].first;
  Sline.insert(s0);
  if(S[s0].a.x!=S[s0].b.x){
    Rmost[n]=S[s0].a;
    Rmost[s0]=S[s0].a;
  }else{
    Rmost[s0]=S[s0].b;
    Rmost[n]=S[s0].b;
  }
//
  set<int, SegOrd>::iterator p,pp;
  for(int i=1;i<2*n;i++){
    if(AB[i].second){//left endpoint
      p=Sline.insert(AB[i].first).first;
      pp=p; pp--;
      Sol.push_back({S[*p].a,Rmost[*pp]});
      if(S[*p].a.x!=S[*p].b.x)
        Rmost[*p]=S[*p].a;
      else
        Rmost[*p]=S[*p].b;
      Rmost[*pp]=S[*p].a;
    }else{//right endpoint
      p=Sline.find(AB[i].first);
      pp=p; pp--;
      Rmost[*pp]=S[*p].b;
      Sline.erase(p);
    }
  }
//
  for(auto ab:Sol)
    cout<<ab.a.x<<" "<<ab.a.y<<" "<<ab.b.x<<" "<<ab.b.y<<"\n";
  return 0;
}

Compilation message

roads.cpp: In member function 'bool SegOrd::operator()(const int&, const int&) const':
roads.cpp:37:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |     return  tua>0 && tub>0 || tva<0 && tvb<0 ||
      |             ~~~~~~^~~~~~~~
roads.cpp:38:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |             tua==0 && tub==0&& tva==0 && tvb==0 && S[u].a.y<S[v].a.y;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
roads.cpp: In function 'void ReadIn()':
roads.cpp:58:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |     if(x1<x2 || x1==x2 && y1<y2)
      |                 ~~~~~~~^~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 141 ms 4716 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 38 ms 1652 KB Output is correct
5 Correct 75 ms 2928 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 37 ms 1652 KB Output is correct
5 Correct 74 ms 2884 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 38 ms 1652 KB Output is correct
10 Correct 424 ms 12892 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 38 ms 1652 KB Output is correct
5 Correct 76 ms 2924 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 41 ms 1776 KB Output is correct
10 Correct 189 ms 6628 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 38 ms 1652 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 39 ms 1652 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 38 ms 1652 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 14 ms 896 KB Output is correct
23 Correct 14 ms 1024 KB Output is correct
24 Correct 28 ms 1268 KB Output is correct
25 Correct 1 ms 384 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 139 ms 4716 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 37 ms 1652 KB Output is correct
7 Correct 75 ms 2924 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 38 ms 1776 KB Output is correct
12 Correct 425 ms 12768 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 37 ms 1652 KB Output is correct
17 Correct 192 ms 6628 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 15 ms 896 KB Output is correct
27 Correct 14 ms 896 KB Output is correct
28 Correct 28 ms 1276 KB Output is correct
29 Correct 187 ms 8420 KB Output is correct
30 Correct 292 ms 11612 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 296 ms 8600 KB Output is correct
33 Correct 291 ms 8548 KB Output is correct
34 Correct 380 ms 11228 KB Output is correct
35 Correct 389 ms 11612 KB Output is correct
36 Correct 316 ms 13776 KB Output is correct