QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224609 | #7511. Planar Graph | ivaziva | WA | 0ms | 3736kb | C++14 | 2.3kb | 2023-10-23 05:24:56 | 2023-10-23 05:24:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long n,m,e;
vector<pair<long long,long long>> vec1;
vector<pair<long long,long long>> vec2;
vector<pair<long long,long long>> seg;
vector<pair<long long,long long>> sred;
vector<pair<double,double>> prave;
int main()
{
ios_base::sync_with_stdio(false);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>e;
for (long long i=1;i<=n;i++)
{
long long x,y;
cin>>x>>y;
vec1.push_back({2*x,2*y});
}
for (long long i=1;i<=m;i++)
{
long long x,y;
cin>>x>>y;
vec2.push_back({2*x,2*y});
}
for (long long i=1;i<=e;i++)
{
long long x,y;
cin>>x>>y;
seg.push_back({x,y});
}
for (long long i=0;i<e;i++)
{
long long tacka1=seg[i].first-1;
long long tacka2=seg[i].second-1;
long long x1=vec1[tacka1].first,y1=vec1[tacka1].second;
long long x2=vec1[tacka2].first,y2=vec1[tacka2].second;
double k=(y2-y1)*1.00/(x2-x1); double t=y1-k*x1;
prave.push_back({k,t});
sred.push_back({(x1+x2)/2,(y1+y2)/2});
}
for (long long i=0;i<e;i++)
{
long long x=sred[i].first,y=sred[i].second;
double da=false;
for (long long j=0;j<m;j++)
{
long long xx=vec2[j].first,yy=vec2[j].second;
double k2=(yy-y)*1.00/(xx-x);
double t2=yy-k2*xx;
double grr=true;
for (long long k=0;k<e;k++)
{
if (k==i) continue;
double k3=prave[k].first;
double t3=prave[k].second;
double xxx=(t3-t2)*1.00/(k2-k3);
double yyy=xxx*k3+t3;
long long t1=seg[k].first-1,t2=seg[k].second-1;
long long x1=vec1[t1].first,y1=vec1[t1].second;
long long x2=vec1[t2].first,y2=vec1[t2].second;
if (yyy>=min(y,yy) and yyy<=max(y,yy) and xxx>=min(xx,x) and xxx<=max(xx,x) and yyy>=min(y1,y2) and yyy<=max(y1,y2) and xxx>=min(x1,x2) and xxx<=max(x1,x2)) {grr=false;break;}
}
if (grr) {da=true;break;}
}
if (da) cout<<1;
else cout<<0;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3736kb
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: 0ms
memory: 3668kb
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:
0111011111111
result:
wrong answer 1st lines differ - expected: '1111111111111', found: '0111011111111'