| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 761713 | alexander707070 | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
struct point{
int x,y;
inline friend bool operator < (point fr,point sc){
return fr.x<sc.x;
}
};
int n,last,cnt,pos,s;
point p[MAXN],endp;
bool used[MAXN];
long long av;
vector< pair<point,point> > v;
point intersec(point a,point b){
return {a.x,b.y};
}
string name[10]={"01.in","02.in","03.in","04.in","05.in","06.in","07.in","08.in","09.in","10.in"};
string eman[10]={"01.out","02.out","03.out","04.out","05.out","06.out","07.out","08.out","09.out","10.out"};
int main(){
fstream cinn,conn;
for(int test=0;test<4;test++){
cinn.open(name[test],ios_base::in);
conn.open(eman[test],ios_base::out);
cinn>>n;
v.clear(); av=0;
for(int i=1;i<=n;i++){
cinn>>p[i].x>>p[i].y;
used[i]=false; av+=p[i].y;
}
av/=n;
sort(p+1,p+n+1);
used[1]=true; endp=p[1];
pos=0; last=1;
cnt=n-1;
while(cnt>0){
s=0;
for(int i=1;i<=n;i++){
if(used[i])continue;
if(pos==0 and !(p[i].y>av and p[last].y<p[i].y) and !(p[i].y<av and p[last].y>p[i].y)){
used[i]=true; cnt--;
v.push_back({endp,intersec(p[i],p[last])});
endp=intersec(p[i],p[last]);
if(p[i].y>p[last].y)pos=1;
else pos=2;
last=i;
}else if(pos==1 and p[i].y>p[last].y){
used[i]=true; cnt--;
v.push_back({endp,intersec(p[last],p[i])});
endp=intersec(p[last],p[i]);
pos=0; last=i;
}else if(pos==2 and p[i].y<p[last].y){
used[i]=true; cnt--;
v.push_back({endp,intersec(p[last],p[i])});
endp=intersec(p[last],p[i]);
pos=0; last=i;
}else{
s=i;
}
}
if(s!=0){
used[s]=true; cnt--;
v.push_back({endp,p[last]});
v.push_back({p[last],intersec(p[s],p[last])});
endp=intersec(p[s],p[last]);
if(p[last].y<p[s].y)pos=1;
else pos=2;
last=s;
}
s=0;
for(int i=n;i>=1;i--){
if(used[i])continue;
if(pos==0 and !(p[i].y>av and p[last].y<p[i].y) and !(p[i].y<av and p[last].y>p[i].y)){
used[i]=true; cnt--;
v.push_back({endp,intersec(p[i],p[last])});
endp=intersec(p[i],p[last]);
if(p[i].y>p[last].y)pos=1;
else pos=2;
last=i;
}else if(pos==1 and p[i].y>p[last].y){
used[i]=true; cnt--;
v.push_back({endp,intersec(p[last],p[i])});
endp=intersec(p[last],p[i]);
pos=0; last=i;
}else if(pos==2 and p[i].y<p[last].y){
used[i]=true; cnt--;
v.push_back({endp,intersec(p[last],p[i])});
endp=intersec(p[last],p[i]);
pos=0; last=i;
}else{
s=i;
}
}
if(s!=0){
used[s]=true; cnt--;
v.push_back({endp,p[last]});
v.push_back({p[last],intersec(p[s],p[last])});
endp=intersec(p[s],p[last]);
if(p[last].y<p[s].y)pos=1;
else pos=2;
last=s;
}
}
v.push_back({endp,p[last]});
v.push_back({p[last],{p[last].x,0}});
v.push_back({{p[last].x,0},{0,0}});
conn<<v.size()+1<<"\n";
for(int i=v.size()-1;i>=0;i--){
conn<<v[i].second.x<<" "<<v[i].second.y<<"\n";
}
conn<<v[0].first.x<<" "<<v[0].first.y<<"\n";
cinn.close();
conn.close();
cout<<test<<" ";
}
/*
cout<<v.size()+1<<"\n";
for(int i=0;i<v.size();i++){
cout<<v[i].first.x<<" "<<v[i].first.y<<" "<<v[i].second.x<<" "<<v[i].second.y<<"\n";
}
cout<<v.back().second.x<<" "<<v.back().second.y<<"\n";
*/
return 0;
}
/**
20
80 32
59 15
54 47
22 84
53 28
68 40
60 11
61 100
16 83
64 20
20 6
32 2
50 98
72 37
66 4
18 94
41 25
97 99
30 86
74 49
*/