QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293861#7511. Planar GraphAlphaMale06RE 0ms0kbC++145.7kb2023-12-29 21:08:382023-12-29 21:08:38

Judging History

你现在查看的是最新测评结果

  • [2023-12-29 21:08:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: