Submission #577648

#TimeUsernameProblemLanguageResultExecution timeMemory
577648juggernautRoads (CEOI20_roads)C++14
15 / 100
209 ms22112 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif pair<ll,ll>a[100005]; pair<ll,ll>b[100005]; int n; const int inf=1e9; bool cmp(pair<pair<ll,ll>,pair<ll,ll>>&l,pair<pair<ll,ll>,pair<ll,ll>>&r){ return l.fr.fr/l.fr.sc<r.fr.fr/r.fr.sc; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc); if(a[1].fr==b[1].fr){ //VERTICAL map<int,vector<int>>mp; for(int i=1;i<=n;i++){ mp[a[i].fr].push_back(a[i].sc); mp[a[i].fr].push_back(b[i].sc); } int prev=inf; for(auto &tmp:mp){ int a=tmp.fr; vector<int>&b=tmp.sc; sort(b.begin(),b.end()); for(int i=1;i+1<(int)b.size();i+=2) printf("%d %d %d %d\n",a,b[i],a,b[i+1]); if(prev^inf) printf("%d %d %d %d\n",prev,mp[prev][0],a,b[0]); prev=a; } }else{ map<pair<ll,ll>,vector<pair<ll,ll>>>mp; for(int i=1;i<=n;i++){ pair<ll,ll>cur; ll &x0=a[i].fr; ll &x1=b[i].fr; ll &y0=a[i].sc; ll &y1=b[i].sc; cur=make_pair(x0*y1-x1*y0,x0-x1); if(cur.sc<0){ cur.fr*=-1; cur.sc*=-1; } ll tmp=__gcd(abs(cur.fr),cur.sc); cur.fr/=tmp; cur.sc/=tmp; mp[cur].push_back(a[i]); mp[cur].push_back(b[i]); } vector<pair<pair<ll,ll>,pair<ll,ll>>>vec; for(auto &tmp:mp){ vector<pair<ll,ll>>&b=tmp.sc; sort(b.begin(),b.end()); for(int i=1;i+1<(int)b.size();i+=2) printf("%lld %lld %lld %lld\n",b[i].fr,b[i].sc,b[i+1].fr,b[i+1].sc); vec.push_back(make_pair(tmp.fr,b[0])); } sort(vec.begin(),vec.end(),cmp); for(int i=1;i<vec.size();i++)printf("%lld %lld %lld %lld\n",vec[i-1].sc.fr,vec[i-1].sc.sc,vec[i].sc.fr,vec[i].sc.sc); } }

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=1;i<vec.size();i++)printf("%lld %lld %lld %lld\n",vec[i-1].sc.fr,vec[i-1].sc.sc,vec[i].sc.fr,vec[i].sc.sc);
      |               ~^~~~~~~~~~~
roads.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
roads.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...