QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293861 | #7511. Planar Graph | AlphaMale06 | RE | 0ms | 0kb | C++14 | 5.7kb | 2023-12-29 21:08:38 | 2023-12-29 21:08:38 |
answer
#include <bits/stdc++.h>
/*
Oce nas,
koji si na nebesima,
da se sveti ime Tvoje,
da dodje carstvo Tvoje,
da bude volja Tvoja,
i na zemlji, kao i na nebu.
Hleb nas nasusni daj nam danas,
i oprosti nam dugove nase,
kao sto i mi oprastamo duznicima svojim,
i ne uvedi nas u iskusenje,
no izbavi nas od zloga.
Jer je Tvoje Carstvo,
i sila, i slava,
u vekove vekova.
Amin.
*/
using namespace std;
typedef vector<int> vc;
typedef vector<vector<int>> vvc;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long
const int N = 101;
struct point{
int x, y, index;
bool equal(point p){
return (p.x==x && p.y==y);
}
};
struct edge{
point a, b;
int index;
void order(){
if(a.x>b.x)swap(a, b);
}
bool equal(edge c){
return (a.index==c.a.index && b.index==c.b.index);
}
};
bool isLeft(point a, point b, point c){
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)>0;
}
struct triangle{
point A, B, C;
edge a, b, c;
int index;
};
bool isin(point A, point B, point C, point p){
bool l1, l2, l3;
l1=isLeft(A, B, p); l2=isLeft(B, C, p); l3=isLeft(C, A, p);
return (l1 == l2 && l2 == l3);
}
bool inter(edge a, edge b){
if(a.a.y<b.a.y)swap(a, b);
return (isLeft(b.a, b.b, a.a) & !isLeft(b.a, b.b, a.b) & isLeft(a.a, a.b, b.b) & !isLeft(a.a, a.b, b.a));
}
bool sharePoint(edge a, edge b){
return (a.a.index==b.a.index||a.a.index==b.b.index||a.b.index==b.a.index||a.b.index==b.b.index);
}
vector<point> spoint;
vector<point> tpoint;
vector<triangle> t;
vector<edge> edges;
pair<int, int> te[1000];
vector<int> marks;
bool exs[N][N];
vector<int> adj[1000];
vector<int> reach;
int indedge[N][N];
bool mark[1000];
bool ans[300];
void dfs(int v){
if(v!=0)reach.pb(v);
mark[v]=1;
for(int to : adj[v]){
if(!mark[to])dfs(to);
}
}
void InputTrianglePoints(int n){
for(int i=0; i< n; i++){
point a;
cin >> a.x >> a.y;
a.index=i;
tpoint.pb(a);
}
}
void InputSourcePoints(int n){
for(int i=0; i< n; i++){
point a;
cin >> a.x >> a.y;
a.index=6969;
spoint.pb(a);
}
}
void InputEdges(int n){
for(int i=0; i< n; i++){
int x, y;
cin >> x >> y;
x--; y--;
edge a;
a.a=tpoint[x];
a.b=tpoint[y];
indedge[x][y]=indedge[y][x]=a.index=edges.size();
a.order();
edges.pb(a);
exs[x][y]=exs[y][x]=1;
}
}
void solve(){
int n, m, e;
cin >> n >> m >> e;
InputTrianglePoints(n);
InputSourcePoints(m);
InputEdges(e);
if(n==2 && e>=1){
cout << 1;
return;
}
//podelis na trouglove (dodas fake edgeve)
for(int i=0; i< n; i++){
for(int j=i+1; j< n; j++){
if(!exs[i][j]){ //nisi do sad dodao taj edge
bool ok=1;
edge ne; ne.a=tpoint[i]; ne.b=tpoint[j]; ne.index=edges.size();
ne.order();
for(edge ed : edges){
if(sharePoint(ed, ne))continue; //ako dele zajednicku tacku to se ne racuna kao da se seku
if(inter(ed, ne)){
ok=0; break;
}
}
if(ok){
edges.pb(ne);
exs[i][j]=exs[j][i]=1;
indedge[i][j]=indedge[j][i]=ne.index;
}
}
}
}
for(int i=0; i<edges.size(); i++){
te[i].F=te[i].S=-1; //za svaki edge samo znas koje trouglove sadrzi
}
//napravis same trouglove
for(int i=0; i< n; i++){
for(int j=i+1; j< n; j++){
for(int k=j+1; k< n; k++){
if(exs[i][j] && exs[i][k] && exs[j][k]){
bool ok=1;
point p1, p2, p3;
p1=tpoint[i]; p2=tpoint[j]; p3=tpoint[k];
for(int l=0; l<n; l++){
if(l!=i && l!=j && l!=k){
if(isin(p1, p2, p3, tpoint[l])){
ok=0;
break;
}
}
}
if(ok){
triangle nt;
nt.A=p1;
nt.B=p2;
nt.C=p3;
nt.index=t.size()+1;
edge a, b, c;
a.a=p2; a.b=p3; a.index=indedge[j][k]; a.order();
b.a=p3; b.b=p1; b.index=indedge[i][k]; b.order();
c.a=p1; c.b=p2; c.index=indedge[i][j]; c.order();
nt.a=a; nt.b=b; nt.c=c;
t.pb(nt);
if(te[a.index].F==-1)te[a.index].F=nt.index;
else te[a.index].S=nt.index;
if(te[b.index].F==-1)te[b.index].F=nt.index;
else te[b.index].S=nt.index;
if(te[c.index].F==-1)te[c.index].F=nt.index;
else te[c.index].S=nt.index;
}
}
}
}
}
//nadjes grane u grafu
for(int i=e; i<edges.size(); i++){ //za svaku fake granu dodas edge
if(te[i].S==-1){ //ako je na obodu dodas izmedju spolja i trougla u kom se nalazi
adj[0].pb(te[i].F);
adj[te[i].F].pb(0);
}
else{ //ako je izmedju 2 trougla dodas izmedju 2 trougla u kojima se nalazi
adj[te[i].F].pb(te[i].S);
adj[te[i].S].pb(te[i].F);
}
}
//nadjes za svaki trougao da li je tacka u njemu, i da li postoji spoljasnja tacka
int cnt=0;
for(int i=0; i< t.size(); i++){
triangle tr = t[i];
bool ok=0;
for(point p : spoint){
if(isin(tr.A, tr.B, tr.C, p)){
cnt++;
ok=1;
}
}
if(ok){
marks.pb(i+1);
}
}
if(cnt!=m){
marks.pb(0);
assert(0);
}
//pustis dfs
for(int strt : marks){
if(!mark[strt]){
dfs(strt);
}
}
if(mark[0]){
//oznacis sve prave grane koje su na ivici
for(int i=0; i< e; i++){
if(te[i].S==-1){
ans[i]=1;
}
}
}
//za svaki trougao do kog mozes da dodjes oznacis sve njegove edgeve
for(int tr : reach){
triangle tri = t[tr-1];
if(tri.a.index<e)ans[tri.a.index]=1;
if(tri.b.index<e)ans[tri.b.index]=1;
if(tri.c.index<e)ans[tri.c.index]=1;
}
for(int i=0; i< e; i++)cout << ans[i];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3