QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297743 | #7511. Planar Graph | sofija6 | WA | 2ms | 3896kb | C++23 | 5.7kb | 2024-01-05 05:54:41 | 2024-01-05 05:54:41 |
Judging History
answer
#include <bits/stdc++.h>
#define ll int
#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[MAXN*MAXN];
bool has[MAXN*MAXN],V[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 l=1;l<lines.size();l++)
{
pair<ll,ll> k=lines[l];
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;
}
}
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: 3800kb
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: 0
Accepted
time: 1ms
memory: 3792kb
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:
1111111111111
result:
ok single line: '1111111111111'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
68 59 168 51 -57 -26 -51 -31 58 -45 -78 -46 -49 -53 14 76 -69 -64 32 58 -49 -1 12 -65 28 -15 -10 29 -53 25 -32 78 -41 24 -37 69 56 54 -10 3 36 -18 46 53 -30 41 -2 -30 13 -58 -37 -20 42 -48 -38 -42 22 64 0 9 -56 7 -11 -66 -23 19 -9 -26 -6 -61 -68 57 13 -13 50 -15 -11 -77 47 -77 57 78 51 -37 56 -75 24...
output:
011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011
result:
ok single line: '011111111111111111100001011000...1111111110011001111111100100011'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
59 1 158 -51 8 50 48 -56 -67 19 7 33 -47 32 44 42 47 -36 -57 15 34 -8 23 -24 43 20 11 61 -41 58 -11 -68 -45 36 -54 -21 42 -28 -49 -28 -31 -34 20 29 -65 -13 38 -22 -36 -30 11 -40 57 64 -69 65 51 47 34 -41 31 -1 35 28 -11 58 58 13 12 -52 43 40 6 46 48 46 -59 -52 30 69 -23 -34 38 -1 -5 -12 -27 -11 24 -...
output:
00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000001000000000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
92 1 125 55 10 67 -85 -26 80 36 -32 44 -64 41 -50 -93 -80 -66 -92 -68 27 -79 9 87 -61 -40 -64 89 100 75 -42 59 40 60 -30 -66 27 63 90 -19 100 24 -20 -13 83 -100 -92 -83 58 -33 -70 74 -20 -55 73 -41 28 27 -31 -37 -22 40 18 -3 -2 70 79 71 29 32 -73 39 -1 17 -95 -61 56 94 -10 -79 -66 -84 87 -16 71 52 4...
output:
10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110
result:
ok single line: '100100100001010010100101001011...0010100000000100011011000000110'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
85 47 204 48 93 -32 10 71 70 -37 10 20 -12 -32 -56 1 -22 -46 -64 56 82 -19 63 -5 83 16 89 79 81 51 -22 43 59 33 -87 28 67 -18 38 -16 -23 18 -78 87 66 -83 29 36 58 6 -2 68 80 18 -34 -17 59 -31 -12 -37 -75 33 -79 -51 -24 -88 6 -19 62 71 -78 -51 72 -49 -45 21 41 -58 33 46 67 -11 -31 62 46 54 55 37 -14 ...
output:
000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011
result:
ok single line: '000110010001001101100010110101...0011001101111010000011001000011'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3892kb
input:
59 96 152 -75886847 147807525 335545968 317138952 262969730 -308175740 91308409 -162085508 -397786268 -191693417 -227565597 195627938 45666011 253210394 -311142459 58197832 -412164189 -270215767 -12639523 -314154358 -269901472 -366179516 -306681757 -167771007 194329800 -339296479 -12501616 -15788817...
output:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
wrong answer 1st lines differ - expected: '011101111111111111101011101110...1110001111100010111110111111111', found: '000000000000000000000000000000...0000000000000000000000000000000'