M_sea

洛谷4049 [JSOI2007]合金
LuoguBZOJ分析极其神仙的题,不看题解根本不会qwq首先,因为$a_i+b_i+c_i=1$,所以可以不管$...
扫描右侧二维码阅读全文
29
2019/01

洛谷4049 [JSOI2007]合金

Luogu

BZOJ

分析

极其神仙的题,不看题解根本不会qwq

首先,因为$a_i+b_i+c_i=1$,所以可以不管$c_i$。然后每种合金就成了一个点。

发现两点能配出的所有合金一定在两点构成的线段上。

问题转为给出$m$个点,求一个以这$m$个点为顶点的边数最少的多边形包含$n$个关键点。

这个东西可以用$\texttt{Floyd}$判最小圈来做?

如果$n$个点都在$(x,y)$左侧,连一条从$x$到$y$的边权为$1$的边。两点不连通当然置$\infty$。

然后跑一遍$\texttt{Floyd}$,答案是$\min\{G[i][i]\}$。

特判所有点重合和共线的情况,前者输出$1$,后者输出$2$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=500+10;
const double EPS=1e-10;

struct Point { double x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
bool operator !=(Point a,Point b) { return fabs(a.x-b.x)>EPS||fabs(a.y-b.y)>EPS; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n,m;
Point a[N],b[N];
int G[N][N];

inline int judge(Point x,Point y) {
    if (x.x>y.x) swap(x,y);
    for (re int i=1;i<=m;++i)
        if (b[i].x<x.x||b[i].x>y.x) return 0;
    if (x.y>y.y) swap(x,y);
    for (re int i=1;i<=m;++i)
        if (b[i].y<x.y||b[i].y>y.y) return 0;
    return 1;
}

inline int check(Point x,Point y) {
    int p=0,q=0;
    for (re int i=1;i<=m;++i) {
        double t=cross(y-x,b[i]-x);
        if (t>EPS) ++p;
        if (t<-EPS) ++q;
        if (p&&q) return 0; //写在里面,不然容易TLE
    }
    if (!p&&!q&&judge(x,y)) { puts("2"); exit(0); } //特判共线
    if (p) return 1;
    else if (q) return 2;
    else return 3;
}

int main() {
    memset(G,0x3f,sizeof(G));
    scanf("%d%d",&n,&m);
    double junk;
    for (re int i=1;i<=n;++i) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&junk);
    for (re int i=1;i<=m;++i) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&junk);
    //特判全部重合
    int f=1;
    for (re int i=1;i<=n;++i) if (a[i]!=a[1]) f=0;
    for (re int i=1;i<=m;++i) if (b[i]!=a[1]) f=0;
    if (f) { puts("1"); return 0; }
    
    for (re int i=1;i<n;++i)
        for (re int j=i+1;j<=n;++j) {
            int flag=check(a[i],a[j]);
            if (flag==1) G[i][j]=1;
            else if (flag==2) G[j][i]=1;
            else if (flag==3) G[i][j]=G[j][i]=1;
        }
    for (re int k=1;k<=n;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
    int ans=2e9;
    for (re int i=1;i<=n;++i) ans=min(ans,G[i][i]);
    if (ans>=0x3f3f3f3f||ans<=2) puts("-1");
    else printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 01 月 29 日 05 : 24 PM

发表评论