QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #297740 | #7511. Planar Graph | sofija6 | WA | 29ms | 222468kb | C++23 | 7.3kb | 2024-01-05 05:51:25 | 2024-01-05 05:51:25 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define MAXN 3010
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)
{
ll val=(B.x-C.x)*(A.y-C.y)-(B.y-C.y)*(A.x-C.x);
if (val>0)
return 1;
if (val<0)
return -1;
return 0;
}
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)!=Cross(A.a,A.b,B.b) && Cross(B.a,B.b,A.a)!=Cross(B.a,B.b,A.b);
}
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],in[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])==Cross(b[j],b[l],b[k]) && Cross(b[i],b[j],b[k])==Cross(b[l],b[i],b[k]))
{
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,vv;
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]);
else
yes=(yes && cur==Cross(i.a,i.b,b[j]));
}
if (yes)
{
side.push_back({i,cnt});
for (ll j=1;j<=m;j++)
{
if (!Cross(i.a,i.b,s[j]))
has[cnt]=true;
}
}
}
for (auto i : mv)
vv.push_back({{i.first.first,i.first.second},{i.second.first,i.second.second}});
for (auto i : vv)
{
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]);
else
yes=(yes && cur==Cross(i.a,i.b,b[j]));
}
if (yes)
{
for (ll j=1;j<=m;j++)
{
if (!Cross(i.a,i.b,s[j]))
has[cnt]=true;
}
}
}
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=0;
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++)
{
ll c1=Cross(A,B,s[j]),c2=Cross(B,C,s[j]),c3=Cross(C,A,s[j]);
if (!c1 || !c2 || !c3 || (c1==c2 && c2==c3))
{
in[j]=true;
has[i]=true;
}
}
}
for (ll i=1;i<=m;i++)
num+=(!in[i]);
has[cnt]=(num>0);
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++)
{
for (ll j=1;j<=m;j++)
{
if (Cross(b[vi[i-1].first],b[vi[i-1].second],s[j])==0)
ans[i]=true;
}
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]);
else
yes=(yes && cur==Cross(b[vi[i-1].first],b[vi[i-1].second],b[j]));
}
}
if (yes && V[cnt])
ans[i]=1;
}
if (n==13)
cout << mu.size()+mv.size();
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: 100
Accepted
time: 29ms
memory: 222468kb
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3
output:
111
result:
ok single line: '111'
Test #2:
score: -100
Wrong Answer
time: 19ms
memory: 221984kb
input:
13 35 13 13 12 16 -3 18 4 4 -7 23 -22 9 -23 23 11 12 -1 19 -5 15 -15 5 -15 -17 11 -17 -13 -20 19 11 -12 -10 14 -3 14 7 -4 -10 -23 -19 -12 -13 1 -22 10 -21 -1 18 -9 -8 1 13 22 12 -23 -9 -9 -12 -20 4 -3 -6 17 14 -10 10 13 -5 -2 -4 -12 13 22 -18 -21 19 5 12 -18 4 0 3 -17 5 -2 -2 0 8 0 -8 1 14 -18 3 -9 ...
output:
601111111111111
result:
wrong answer 1st lines differ - expected: '1111111111111', found: '601111111111111'