QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188882#7511. Planar GraphHDUT01#TL 1ms22380kbC++145.2kb2023-09-26 16:03:192023-09-26 16:03:19

Judging History

你现在查看的是最新测评结果

  • [2023-09-26 16:03:19]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:22380kb
  • [2023-09-26 16:03:19]
  • 提交

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;
}

詳細信息

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...

output:


result: