HRY and cats

C++14(g++5.4) 解法, 执行用时: 145ms, 内存消耗: 640K, 提交时间: 2019-04-28 13:17:25

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&-x)
#define sqr(x) ((x)*(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
const int maxn=305;
struct point {
    ll x,y;
    point() {}
    point(ll x,ll y):x(x),y(y) {}
    point operator-(const point b) const {
        return point(x-b.x,y-b.y);
    }
    void input() {
        scanf("%lld%lld",&x,&y);
    }
} cat[maxn],stump[maxn];
ll cross(point a,point b) {
    return a.x*b.y-a.y*b.x;
}
ll dot(point a,point b) {
    return a.x*b.x+a.y*b.y;
}
int n,m;
vector<int> e[maxn];
int ans;
bool vis[maxn];
queue<pii> q;
void gao(int start) {
    mem(vis,0);
    while(!q.empty()) q.pop();
    int len=(int)e[start].size();
    rep(i,0,len-1) {
        q.push(mp(e[start][i],1));
        vis[e[start][i]]=1;
    }
    while(!q.empty()) {
        pii p=q.front();
        q.pop();
        if(p.fi==start) {
            if(ans==-1||ans>p.se) ans=p.se;
            break;
        }
        int len=(int)e[p.fi].size();
        rep(i,0,len-1) {
            int v=e[p.fi][i];
            if(vis[v]) continue;
            vis[v]=1;
            q.push(mp(v,p.se+1));
        }
    }
}

int main() {
    int caseCnt;
    scanf("%d",&caseCnt);
    while(caseCnt--) {
        scanf("%d%d",&n,&m);
        rep(i,1,m) e[i].clear();
        rep(i,1,n) cat[i].input();
        rep(i,1,m) stump[i].input();
        rep(i,1,m) {
            rep(j,1,m) {
                if(i==j) continue;
                bool ok=true;
                rep(k,1,n) {
                    if(cross(stump[j]-stump[i],cat[k]-stump[i])<=0) {
                        ok=false;
                        break;
                    }
                }
                if(ok) e[i].pb(j);
            }
        }
        ans=-1;
        rep(i,1,m) gao(i);
        printf("%d\n",ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 356ms, 内存消耗: 888K, 提交时间: 2019-04-27 21:29:18

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define X first
#define Y second
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 300+10;
const double eps = 1e-9;
pair<ll,ll> cat[maxn],pt[maxn];
int G[maxn][maxn];
ll cross(pair<ll,ll> &a,pair<ll,ll> &b){
    return a.X*b.Y-a.Y*b.X;
}
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T; cin>>T;
    while (T--){
        int n,m; cin>>n>>m;
        for (int i=0;i<n;i++) cin>>cat[i].X>>cat[i].Y;
        for (int i=0;i<m;i++) cin>>pt[i].X>>pt[i].Y;
        mst(G,0x3f);
        for (int i=0;i<m;i++) for (int j=0;j<m;j++){
            if (i==j) {
                G[i][j]=0;
                continue;
            }
            pair<ll,ll> v1(pt[j].X-pt[i].X,pt[j].Y-pt[i].Y),v2;
            bool flag=true;
            for (int k=0;k<n;k++){
                v2.X=pt[i].X-cat[k].X;
                v2.Y=pt[i].Y-cat[k].Y;
                if (cross(v1,v2)>=0){
                    flag=false;
                    break;
                }
            }
            if (flag) G[i][j]=1;
        }
        for (int k=0;k<m;k++) for (int i=0;i<m;i++) for (int j=0;j<m;j++){
            G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
        }
        int ans=inf;
        for (int i=0;i<m;i++) for (int j=0;j<m;j++){
            if (i==j) continue;
            ans=min(ans,G[i][j]+G[j][i]);
        }
        if (ans<inf) cout<<ans<<"\n"; else cout<<-1<<"\n";
    }
    return 0;
}

详情