QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297735 | #7511. Planar Graph | sofija6 | WA | 1ms | 4140kb | C++23 | 6.0kb | 2024-01-05 05:42:12 | 2024-01-05 05:42:12 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define MAXN 110
using namespace std;
struct point
{
ll X,Y;
};
struct segment
{
point A,B;
};
struct triangle
{
ll iA,iB,iC;
};
point b[MAXN],s[MAXN];
vector<pair<ll,ll> > lines,out;
ll n,m,e,p[3*MAXN],q[3*MAXN],edge[MAXN][MAXN],ind,ans[3*MAXN];
vector<ll> G[2*MAXN*MAXN];
bool has[2*MAXN*MAXN],V[2*MAXN*MAXN];
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;
}
bool Same_Points(point a,point b)
{
return (a.X==b.X && a.Y==b.Y);
}
bool Intersect(segment a,segment b)
{
if (Same_Points(a.A,b.A) || Same_Points(a.A,b.B) || Same_Points(a.B,b.A) || Same_Points(a.B,b.B))
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));
}
void Draw_Lines()
{
for (ll i=1;i<=n;i++)
{
for (ll j=i+1;j<=n;j++)
{
if (edge[i][j])
continue;
bool yes=true;
for (ll i=1;i<lines.size();i++)
{
pair<ll,ll> k=lines[i];
if (Intersect({b[i],b[j]},{b[k.first],b[k.second]}))
{
yes=false;
break;
}
}
if (yes)
{
edge[i][j]=lines.size();
edge[j][i]=lines.size();
lines.push_back({i,j});
}
}
}
}
vector<triangle> t;
bool Check(ll i,ll j,ll k)
{
for (ll l=1;l<=n;l++)
{
if (i==l || j==l || k==l)
continue;
if (Cross(b[i],b[j],b[l])==Cross(b[j],b[k],b[l]) && Cross(b[i],b[j],b[l])==Cross(b[k],b[i],b[l]))
return false;
}
return true;
}
void Get_Triangles()
{
for (ll i=1;i<=n;i++)
{
for (ll j=i+1;j<=n;j++)
{
for (ll k=j+1;k<=n;k++)
{
if (edge[i][j] && edge[j][k] && edge[k][i] && Check(i,j,k))
t.push_back({i,j,k});
}
}
}
}
void Get_Out_Lines()
{
for (ll l=1;l<lines.size();l++)
{
pair<ll,ll> i=lines[l];
ll cur=0;
bool yes=true;
for (ll j=1;j<=n;j++)
{
if (j==i.first || j==i.second)
continue;
if (!cur)
cur=Cross(b[i.first],b[i.second],b[j]);
else if (cur!=Cross(b[i.first],b[i.second],b[j]))
{
yes=false;
break;
}
}
if (yes)
out.push_back(i);
}
}
void Create_Graph()
{
map<ll,vector<ll> > mp;
for (ll i=1;i<t.size();i++)
{
ll a=t[i].iA,b=t[i].iB,c=t[i].iC;
if (edge[a][b]>e)
mp[edge[a][b]].push_back(i);
if (edge[b][c]>e)
mp[edge[b][c]].push_back(i);
if (edge[c][a]>e)
mp[edge[c][a]].push_back(i);
}
for (auto i : mp)
{
if (i.second.size()==1)
{
G[ind].push_back(i.second[0]);
G[i.second[0]].push_back(ind);
}
else
{
G[i.second[1]].push_back(i.second[0]);
G[i.second[0]].push_back(i.second[1]);
}
}
}
void Contains_Source()
{
bool in[m+2]={false};
for (ll i=1;i<t.size();i++)
{
ll aa=t[i].iA,bb=t[i].iB,cc=t[i].iC;
for (ll j=1;j<=m;j++)
{
ll c1=Cross(b[aa],b[bb],s[j]),c2=Cross(b[bb],b[cc],s[j]),c3=Cross(b[cc],b[aa],s[j]);
set<ll> ss;
ss.insert(c1);
ss.insert(c2);
ss.insert(c3);
if (ss.count(0))
ss.erase(0);
if (ss.size()==1)
{
in[j]=true;
has[i]=true;
}
}
}
for (ll i=1;i<=m;i++)
{
if (!in[i])
has[ind]=true;
}
for (ll i=1;i<out.size();i++)
{
pair<ll,ll> j=out[i];
if (edge[j.first][j.second]>e)
{
for (ll l=1;l<=m;l++)
{
if (!Cross(b[j.first],b[j.second],s[l]))
has[ind]=true;
}
}
}
}
void Solve()
{
queue<ll> q;
for (ll i=1;i<=ind;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])
{
q.push(next);
V[next]=true;
}
}
}
for (ll i=1;i<ind;i++)
{
if (V[i])
{
ll aa=t[i].iA,bb=t[i].iB,cc=t[i].iC;
if (edge[aa][bb]<=e)
ans[edge[aa][bb]]=true;
if (edge[cc][bb]<=e)
ans[edge[cc][bb]]=true;
if (edge[aa][cc]<=e)
ans[edge[aa][cc]]=true;
}
}
if (V[ind])
{
for (auto i : out)
{
ll aa=i.first,bb=i.second;
if (edge[aa][bb]<=e)
ans[edge[aa][bb]]=true;
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
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;
lines.push_back({0,0});
t.push_back({0,0,0});
out.push_back({0,0});
for (ll i=1;i<=e;i++)
{
cin >> p[i] >> q[i];
lines.push_back({p[i],q[i]});
edge[p[i]][q[i]]=i;
edge[q[i]][p[i]]=i;
}
Draw_Lines();
Get_Triangles();
Get_Out_Lines();
ind=t.size();
Create_Graph();
Contains_Source();
Solve();
for (ll i=1;i<=e;i++)
cout << ans[i];
return 0;
}
/**
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
**/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4048kb
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: 1ms
memory: 4140kb
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:
1000100100000
result:
wrong answer 1st lines differ - expected: '1111111111111', found: '1000100100000'