# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
103579 | kishtarn555 | Konj (COCI19_konj) | C++14 | 82 ms | 9848 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<iostream>
#include<map>
#include<set>
#include<vector>
using namespace std;
int N;
struct line{
int x1,y1,x2,y2;
bool operator < (const line & o) const {
if (x1!=o.x1)
return x1<o.x1;
if (x2!=o.x2)
return x2<o.x2;
if (y1!=o.y1)
return y1<o.y1;
return y2<o.y2;
}
};
line traces[200005];
bool visited[200005];
bool indraw[200005];
vector<int> adj[303][303];
bool drawing[303][303];
int x,y;
bool inside(int index) {
// return true;
if (x < min (traces[index].x1,traces[index].x2) ||x > max (traces[index].x1,traces[index].x2))
return false;
if (y < min (traces[index].y1,traces[index].y2) ||y > max (traces[index].y1,traces[index].y2))
return false;
return true;
}
bool dfs(int cur) {
if (visited[cur])return indraw[cur];
visited[cur]=true;
if(inside(cur))return indraw[cur]=true;
int ni;
for (int i = 0; i < adj[traces[cur].x1][traces[cur].y1].size(); i++) {
ni = adj[traces[cur].x1][traces[cur].y1][i];
if (cur==ni)continue;
indraw[cur]=indraw[cur]||dfs(ni);
}
for (int i = 0; i < adj[traces[cur].x2][traces[cur].y2].size(); i++) {
ni = adj[traces[cur].x2][traces[cur].y2][i];
if (cur==ni)continue;
indraw[cur]=indraw[cur]||dfs(ni);
}
return indraw[cur];
}
int mx=304,my=304,xx=-1,yy=-1;
void draw(int index) {
if (traces[index].x1==traces[index].x2) {
int fini = max(traces[index].y1,traces[index].y2);
mx=min(traces[index].x1,mx);
xx=max(traces[index].x1,xx);
int x =traces[index].x1;
for (int y = min(traces[index].y1,traces[index].y2);y<=fini; y++) {
drawing[x][y]=true;
my=min(y,my);
yy=max(y,yy);
}
return;
}
int fini = max(traces[index].x1,traces[index].x2);
my=min(traces[index].y1,my);
yy=max(traces[index].y1,yy);
int y =traces[index].y1;
for (int x = min(traces[index].x1,traces[index].x2);x<=fini; x++) {
drawing[x][y]=true;
mx=min(x,mx);
xx=max(x,xx);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >>N;
for (int i = 0; i < N; i++) {
cin >> traces[i].x1>>traces[i].y1>>traces[i].x2>>traces[i].y2;
adj[traces[i].x1][traces[i].y1].push_back(i);
adj[traces[i].x2][traces[i].y2].push_back(i);
}
cin >> x >> y;
for (int i = 0; i < N; i ++) {
if (dfs(i)) {
draw(i);
}
}
for (int y = yy; y>=my; y--){
for (int x = mx; x <= xx; x++)
cout << (drawing[x][y]?"#":".");
cout << "\n";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |