QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297652 | #7511. Planar Graph | sofija6 | ML | 0ms | 0kb | C++23 | 6.2kb | 2024-01-04 21:44:56 | 2024-01-04 21:44:58 |
answer
#include <bits/stdc++.h>
#define ll long long
#define MAXN 5010
using namespace std;
struct point
{
ll x,y;
};
struct segment
{
point a,b;
};
struct triangle
{
ll ia,ib,ic;
};
segment Sortt(segment s)
{
if (s.a.x>s.b.x || (s.a.x==s.b.x && s.a.y>s.b.y))
swap(s.a,s.b);
return s;
}
ll Cross(point C,point B,point A)
{
return (B.x-C.x)*(A.y-C.y)-(B.y-C.y)*(A.x-C.x);
}
pair<pair<ll,ll>,pair<ll,ll> > Make_Pair(segment A)
{
return {{A.a.x,A.a.y},{A.b.x,A.b.y}};
}
bool Intersect(segment A,segment B)
{
if (A.a.x==B.a.x && A.a.y==B.a.y)
return false;
if (A.b.x==B.b.x && A.b.y==B.b.y)
return false;
if (A.a.x==B.b.x && A.a.y==B.b.y)
return false;
if (A.b.x==B.a.x && A.b.y==B.a.y)
return false;
return (Cross(A.a,A.b,B.a)>0)!=(Cross(A.a,A.b,B.b)>0) && (Cross(B.a,B.b,A.a)>0)!=(Cross(B.a,B.b,A.b)>0);
}
bool Cmp(pair<segment,ll> A,pair<segment,ll> B)
{
return Make_Pair(A.first)<Make_Pair(B.first);
}
vector<segment> v,u;
vector<triangle> t;
set<pair<pair<ll,ll>,pair<ll,ll> > > mv,mu;
vector<pair<segment,ll> > side;
bool Exist(segment A)
{
pair<pair<ll,ll>,pair<ll,ll> > p=Make_Pair(A);
return (mv.count(p) || mu.count(p));
}
point b[MAXN],s[MAXN];
vector<ll> G[MAXN*MAXN];
bool has[MAXN*MAXN],V[MAXN*MAXN];
ll ans[MAXN],edge[MAXN][MAXN];
vector<pair<ll,ll> > vi;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,m,e;
cin >> n >> m >> e;
for (ll i=1;i<=n;i++)
cin >> b[i].x >> b[i].y;
for (ll i=1;i<=m;i++)
cin >> s[i].x >> s[i].y;
for (ll i=1;i<=e;i++)
{
ll p,q;
cin >> p >> q;
v.push_back({b[p],b[q]});
mv.insert(Make_Pair({b[p],b[q]}));
mv.insert(Make_Pair({b[q],b[p]}));
edge[p][q]=i;
edge[q][p]=i;
vi.push_back({p,q});
}
for (ll i=1;i<=n;i++)
{
for (ll j=i+1;j<=n;j++)
{
if (mv.count(Make_Pair({b[i],b[j]})) || mu.count(Make_Pair({b[i],b[j]})))
continue;
bool yes=true;
for (auto l : v)
yes=(yes && !Intersect(l,{b[i],b[j]}));
for (auto l : u)
yes=(yes && !Intersect(l,{b[i],b[j]}));
if (yes)
{
u.push_back({b[i],b[j]});
mu.insert(Make_Pair({b[i],b[j]}));
mu.insert(Make_Pair({b[j],b[i]}));
}
}
}
t.push_back({0,0,0});
ll cnt=1;
for (ll i=1;i<=n;i++)
{
for (ll j=i+1;j<=n;j++)
{
for (ll l=j+1;l<=n;l++)
{
segment A={b[i],b[j]},B={b[j],b[l]},C={b[l],b[i]};
bool yes=true;
for (ll k=1;k<=n;k++)
{
if (k!=i && k!=j && k!=l)
{
if ((Cross(b[i],b[j],b[k])>0)==(Cross(b[j],b[l],b[k])>0) && (Cross(b[i],b[j],b[k])>0)==(Cross(b[l],b[i],b[k])>0))
{
yes=false;
break;
}
}
}
if (yes && Exist(A) && Exist(B) && Exist(C))
{
t.push_back({i,j,l});
if (mu.count(Make_Pair(A)))
side.push_back({A,cnt});
if (mu.count(Make_Pair(B)))
side.push_back({B,cnt});
if (mu.count(Make_Pair(C)))
side.push_back({C,cnt});
cnt++;
}
}
}
}
vector<segment> vu;
for (auto i : mu)
vu.push_back({{i.first.first,i.first.second},{i.second.first,i.second.second}});
for (auto i : vu)
{
ll cur=-1;
bool yes=true;
for (ll j=1;j<=n;j++)
{
if (i.a.x==b[j].x && i.a.y==b[j].y)
continue;
if (i.b.x==b[j].x && i.b.y==b[j].y)
continue;
if (cur==-1)
cur=(Cross(i.a,i.b,b[j])>0);
else
yes=(yes && cur==(Cross(i.a,i.b,b[j])>0));
}
if (yes)
side.push_back({i,cnt});
}
for (ll i=0;i<side.size();i++)
side[i].first=Sortt(side[i].first);
sort(side.begin(),side.end(),Cmp);
for (ll i=0;i<side.size();i+=2)
{
G[side[i].second].push_back(side[i+1].second);
G[side[i+1].second].push_back(side[i].second);
}
ll num=m;
for (ll i=1;i<t.size();i++)
{
point A=b[t[i].ia],B=b[t[i].ib],C=b[t[i].ic];
for (ll j=1;j<=m;j++)
{
if ((Cross(A,B,s[j])>0)==(Cross(B,C,s[j])>0) && (Cross(A,B,s[j])>0)==(Cross(C,A,s[j])>0))
{
has[i]=true;
num--;
}
}
}
if (num)
has[cnt]=true;
queue<ll> q;
for (ll i=1;i<=cnt;i++)
{
if (has[i])
{
q.push(i);
V[i]=true;
}
}
while (!q.empty())
{
ll i=q.front();
q.pop();
for (ll next : G[i])
{
if (!V[next])
{
V[next]=true;
q.push(next);
}
}
}
for (ll i=1;i<t.size();i++)
{
if (V[i])
{
ans[edge[t[i].ia][t[i].ib]]=1;
ans[edge[t[i].ic][t[i].ib]]=1;
ans[edge[t[i].ia][t[i].ic]]=1;
}
}
for (ll i=1;i<=e;i++)
{
if (ans[i])
continue;
ll cur=-1;
bool yes=true;
for (ll j=1;j<=n;j++)
{
if (j!=vi[i-1].first && j!=vi[i-1].second)
{
if (cur==-1)
cur=(Cross(b[vi[i-1].first],b[vi[i-1].second],b[j])>0);
else
yes=(yes && cur==(Cross(b[vi[i-1].first],b[vi[i-1].second],b[j])>0));
}
}
if (yes && V[cnt])
ans[i]=1;
}
for (ll i=1;i<=e;i++)
cout << ans[i];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3
output:
111