【bzoj1027】合金
分析
数形结合+计算几何+Floyd最小环。
http://blog.csdn.net/popoqqq/article/details/40539273
虽然这样占大家的很不好,但是我的确需要这么做。
小结
(1)最小环的写法
(2)凸包的一种简易算法
RT。
(3)关于计算几何的练习
通过做这道题,计算几何的模板也熟悉了一些。
计算几何如何调试?
这个么...好像只能瞪眼法了。
代码
#include <cstdio>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
const int M=512;
const int N=512;
const int MAX=INT_MAX>>1;
const double EPS=1e-15;
int cmp(double x);
int m,n;
struct point
{
double x,y;
point(double _x=0,double _y=0) {
x=_x,y=_y;
}
friend point operator - (point a,point b) {
return point(a.x-b.x,a.y-b.y);
}
friend point operator * (point a,point b) {
return point(a.x*b.x,a.y*b.y);
}
friend int operator == (point a,point b) {
return !cmp(a.x-b.x)&&!cmp(a.y-b.y);
}
friend int operator != (point a,point b) {
return !(a==b);
}
}mer[M],prd[N];
int f[M][M];
int res;
void Init(void) {
scanf("%d%d",&m,&n);
rep(i,1,m) {
double x,y; scanf("%lf%lf%*lf",&x,&y);
mer[i]=point(x,y);
}
rep(i,1,n) {
double x,y; scanf("%lf%lf%*lf",&x,&y);
prd[i]=point(x,y);
}
}
int cmp(double x)
{
if(fabs(x)<EPS) return 0;
return x>0?1:-1;
}
double det(point a,point b) {
return a.x*b.y-a.y*b.x;
}
int Left(point k,point a,point b) {
double t=det(b-a,k-a);
return t>0;
}
int On(point k,point a,point b) {
if (cmp(det(k-a,b-a))!=0) return 0;
if (!(cmp(min(a.x,b.x)-k.x)<=0&&cmp(k.x-max(a.x,b.x))<=0)) return 0;
if (!(cmp(min(a.y,b.y)-k.y)<=0&&cmp(k.y-max(a.y,b.y))<=0)) return 0;
return 1;
}
/*
bool On(const point &a,const point &b,const point &c) {
return !cmp(det(a-b,c-b))&&cmp((a.x-b.x)*(a.x-c.x))<=0&&cmp((a.y-b.y)*(a.y-c.y))<=0;
}
*/
int Check(point a,point b) {
rep(i,1,n) {
int t1=Left(prd[i],a,b);
int t2=On(prd[i],a,b);
if (!t1&&!t2) return 0;
}
return 1;
}
void MakeGraph(void) {
rep(i,1,m) rep(j,1,m) f[i][j]=MAX;
rep(i,1,m) rep(j,1,m)
if (Check(mer[i],mer[j]))
f[i][j]=1;
}
int Floyd(void) {
rep(i,1,m) {
int mrk=1;
rep(j,1,n) if (mer[i]!=prd[j]) {
mrk=0;
break;
}
if (mrk) return 1;
}
rep(i,1,m) rep(j,1,m) {
int mrk=1;
rep(k,1,n)
if (!On(prd[k],mer[i],mer[j])) {
mrk=0;
break;
}
if (mrk) return 2;
}
/*
rep(i,1,m) {
rep(j,1,m)
if (f[i][j]!=MAX)
printf("%d ",f[i][j]);
else printf("0 ");
printf("\n");
}
*/
int ans=MAX;
rep(k,1,m) rep(i,1,m) rep(j,1,m)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
rep(i,1,m) ans=min(ans,f[i][i]);
return ans!=MAX?ans:-1;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("bzoj1027.in","r",stdin);
freopen("bzoj1027.out","w",stdout);
#endif
Init();
MakeGraph();
res=Floyd();
printf("%d\n",res);
return 0;
}