1 条题解

  • 1
    @ 2022-7-21 21:29:36
    #include <bits/stdc++.h>
    #define db long double
    #define eps 1e-7
    using namespace std;
    const int N = 505,M = 505;
    struct point{
    	db x,y;
    	point(db xx=0,db yy=0){ x = xx,y = yy; }
    	bool operator < (const point w) const{
    		if (fabs(x-w.x) > eps) return x < w.x;
    		if (fabs(y-w.y) > eps) return y < w.x;
    		return 0;
    	}
    }a[N],b[M];
    bool operator == (point a,point b){ return fabs(a.x-b.x) < eps && fabs(a.y-b.y) < eps; }
    point operator + (point a,point b){ return point(a.x+b.x,a.y+b.y); }
    point operator - (point a,point b){ return point(a.x-b.x,a.y-b.y); }
    inline db operator * (point a,point b){ return a.x * b.y - a.y * b.x; }
    inline bool left(point a,point b,point p){ return fabs((b-a) * (p-a)) > eps && ((b-a) * (p-a)) > eps;  }
    int n,m,dp[N][N],ans;
    inline bool check(point p1,point p2){
    	if (p1 == p2) return 0;
    	for (int i = 1; i <= m; ++i) if (left(p1,p2,b[i])) return 0;
    	for (int i = 1; i <= m; ++i) if (fabs((p2-p1)*(b[i]-p1)) < eps){
    		if (p1 == b[i] || p2 == b[i]) continue;
    		db l,r;
    		l = p1.x,r = p2.x; if (l > r) swap(l,r); if (l-eps > b[i].x || b[i].x > r+eps) return 0;
    		l = p1.y,r = p2.y; if (l > r) swap(l,r); if (l-eps > b[i].y || b[i].y > r+eps) return 0;
    	}
    	return 1;
    }
    int main(){
    	int i,j,k;
    	cin >> n >> m;
    	for (i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[0].x; sort(a+1,a+n+1);
    	for (i = 1; i <= m; ++i) cin >> b[i].x >> b[i].y >> a[0].x; sort(b+1,b+m+1);
    	for (i = 1; i <= n; ++i) a[i].x *= 1000000,a[i].y *= 1000000;
    	for (i = 1; i <= m; ++i) b[i].x *= 1000000,b[i].y *= 1000000;
    	n = unique(a+1,a+n+1) - (a+1);
    	m = unique(b+1,b+m+1) - (b+1);
    	for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) dp[i][j] = 10000000;
    	ans = 10000000;
    	for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j)
    		if (i != j && check(a[i],a[j])) dp[i][j] = 1;
    	for (k = 1; k <= n; ++k) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j)
    		dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
    	for (i = 1; i <= n; ++i) ans = min(ans,dp[i][i]);
    	if (n == 1 && m == 1 && a[1] == b[1]) ans = 1;
    	if (ans > n) cout << -1 << '\n'; else cout << ans << '\n';
    	return 0;
    }
    
    • 1

    信息

    ID
    2981
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    1
    已通过
    0
    上传者