QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188882 | #7511. Planar Graph | HDUT01# | TL | 1ms | 22380kb | C++14 | 5.2kb | 2023-09-26 16:03:19 | 2023-09-26 16:03:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
struct jz{
int x,y;
}e[305];
using _T=double; //全局数据类型,可修改为 long long 等
constexpr _T eps=1e-8;
constexpr long double PI=3.1415926535897932384l;
// 点与向量
template<typename T> struct point
{
T x,y;
bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const point &a) const {return !(*this<a || *this==a);}
point operator+(const point &a) const {return {x+a.x,y+a.y};}
point operator-(const point &a) const {return {x-a.x,y-a.y};}
point operator-() const {return {-x,-y};}
point operator*(const T k) const {return {k*x,k*y};}
point operator/(const T k) const {return {x/k,y/k};}
T operator*(const point &a) const {return x*a.x+y*a.y;} // 点积
T operator^(const point &a) const {return x*a.y-y*a.x;} // 叉积,注意优先级
int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // to-left 测试
T len2() const {return (*this)*(*this);} // 向量长度的平方
T dis2(const point &a) const {return (a-(*this)).len2();} // 两点距离的平方
// 涉及浮点数
long double len() const {return sqrtl(len2());} // 向量长度
long double dis(const point &a) const {return sqrtl(dis2(a));} // 两点距离
long double ang(const point &a) const {return acosl(max(-1.0,min(1.0,((*this)*a)/(len()*a.len()))));} // 向量夹角
point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 逆时针旋转(给定角度)
point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 逆时针旋转(给定角度的正弦与余弦)
};
using Point=point<_T>;
// 直线
template<typename T> struct line
{
point<T> p,v; // p 为直线上一点,v 为方向向量
bool operator==(const line &a) const {return v.toleft(a.v)==0 && v.toleft(p-a.p)==0;}
int toleft(const point<T> &a) const {return v.toleft(a-p);} // to-left 测试
// 涉及浮点数
point<T> inter(const line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));} // 直线交点
long double dis(const point<T> &a) const {return abs(v^(a-p))/v.len();} // 点到直线距离
point<T> proj(const point<T> &a) const {return p+v*((v*(a-p))/(v*v));} // 点在直线上的投影
};
using Line=line<_T>;
//线段
template<typename T> struct segment
{
point<T> a,b;
// 判定性函数建议在整数域使用
// 判断点是否在线段上
// -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
int is_on(const point<T> &p) const
{
if (p==a || p==b) return -1;
return (p-a).toleft(p-b)==0 && (p-a)*(p-b)<-eps;
}
// 判断线段直线是否相交
// -1 直线经过线段端点 | 0 线段和直线不相交 | 1 线段和直线严格相交
int is_inter(const line<T> &l) const
{
if (l.toleft(a)==0 || l.toleft(b)==0) return -1;
return l.toleft(a)!=l.toleft(b);
}
// 判断两线段是否相交
// -1 在某一线段端点处相交 | 0 两线段不相交 | 1 两线段严格相交
int is_inter(const segment<T> &s) const
{
if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
const line<T> l{a,b-a},ls{s.a,s.b-s.a};
return l.toleft(s.a)*l.toleft(s.b)==-1 && ls.toleft(a)*ls.toleft(b)==-1;
}
};
using Segment=segment<_T>;
Point a[105],b[105],c[305];
vector<int> lnk[105];
int pd[105],tot,vis[105],s[105],top;
int w[405][100005];
int pre(int x){if (x==1) return top;return x-1;}
int nxt(int x){if (x==top) return 1;return x+1;}
int check(Point x){
int num=0;
Segment l={x,Point{x.x,1e9}};
for (int i=1;i<=top;i++){
Segment r={a[s[i]],a[s[nxt(i)]]};
if (r.is_on(x)==1) return 2;
if (l.is_inter(r)==1) num++;
else if (l.is_inter(r)==-1){
if (l.is_on(a[s[i]])!=0){
r={a[s[pre(i)]],a[s[nxt(i)]]};
Line ll={l.a,l.b-l.a};
if (r.is_inter(ll)!=0) num++;
}
}
}
return num%2;
}
void work(){
++tot;
for (int i=1;i<=k;i++) w[i][tot]=check(b[i]);
for (int i=1;i<=m;i++) w[k+i][tot]=check(c[i]);
}
void DFS(int x,int y,int z){
s[++top]=x;
vis[x]=1;
for (auto j:lnk[x])
if (!pd[j]&&j!=y){
if (j==z) work();
if (!vis[j]) DFS(j,x,z);
}
vis[x]=0;
--top;
}
int main(){
scanf("%d%d%d",&n,&k,&m);
for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for (int i=1;i<=k;i++) scanf("%lf%lf",&b[i].x,&b[i].y);
for (int i=1;i<=m;i++){
scanf("%d%d",&e[i].x,&e[i].y);
c[i].x=(a[e[i].x].x+a[e[i].y].x)/2;
c[i].y=(a[e[i].x].y+a[e[i].y].y)/2;
lnk[e[i].x].push_back(e[i].y);
lnk[e[i].y].push_back(e[i].x);
}
for (int i=1;i<=n;i++){
DFS(i,0,i);
pd[i]=1;
}
for (int i=1;i<=m;i++){
int ans=0;
for (int j=1;j<=k;j++){
for (int t=1;t<=tot;t++){
if (w[k+i][t]!=2&&w[j][t]!=w[k+i][t]) break;
if (t==tot) ans=1;
}
if (ans==1) break;
}
printf("%d",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6036kb
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: 0ms
memory: 22380kb
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: -100
Time Limit Exceeded
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...