Bzoj1185 [hnoi2007]最小矩形覆盖

细节超多的计几题

Posted by yjjr's blog on February 10, 2018

6 1.0 3.00000

1 4.00000

2.0000 1

3 0.0000

3.00000 6

6.0 3.0

18.00000

3.00000 0.00000

6.00000 3.00000

3.00000 6.00000

0.00000 3.00000

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-9
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e4+6;
double ans=1e60;int n,top,k=0;
struct P{
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
friend bool operator < (P a,P b){return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;}
friend bool operator == (P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
friend bool operator != (P a,P b){return !(a==b);}
friend P operator + (P a,P b){return P(a.x+b.x,a.y+b.y);}
friend P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
friend double operator * (P a,P b){return a.x*b.y-a.y*b.x;}
friend P operator * (P a,double b){return P(a.x*b,a.y*b);}
friend double operator/(P a,P b){return a.x*b.x+a.y*b.y;}
friend double dis(P a){return sqrt(a.x*a.x+a.y*a.y);}
}p[maxn],s[maxn],a[6];
bool cmp(P a,P b){
double t=(a-p[1])*(b-p[1]);
if(fabs(t)<eps)return dis(p[1]-a)-dis(p[1]-b)<0;else return t>0;
}
void graham(){
rep(i,2,n)if(p[i]<p[1])swap(p[i],p[1]);
sort(p+2,p+n+1,cmp);
s[++top]=p[1];
rep(i,2,n){
while(top>1&&((s[top]-s[top-1])*(p[i]-s[top]))<eps)top--;
s[++top]=p[i];
}
s[0]=s[top];
}
void RC(){
int l=1,r=1,p=1;double L,R,D,H;
rep(i,0,top-1){
D=dis(s[i]-s[i+1]);
while((s[i+1]-s[i])*(s[p+1]-s[i])-(s[i+1]-s[i])*(s[p]-s[i])>-eps)p=(p+1)%top;
while((s[i+1]-s[i])/(s[r+1]-s[i])-(s[i+1]-s[i])/(s[r]-s[i])>-eps)r=(r+1)%top;
if(i==0)l=r;
while((s[i+1]-s[i])/(s[l+1]-s[i])-(s[i+1]-s[i])/(s[l]-s[i])<eps)l=(l+1)%top;
L=(s[i+1]-s[i])/(s[l]-s[i])/D,R=(s[i+1]-s[i])/(s[r]-s[i])/D;
H=(s[i+1]-s[i])*(s[p]-s[i])/D;
if(H<0)H=-H;
double tmp=(R-L)*H;
if(tmp<ans){
ans=tmp;
a[0]=s[i]+(s[i+1]-s[i])*(R/D);
a[1]=a[0]+(s[r]-a[0])*(H/dis(a[0]-s[r]));
a[2]=a[1]-(a[0]-s[i])*((R-L)/dis(s[i]-a[0]));
a[3]=a[2]-(a[1]-a[0]);
}
}
}
int main()
{