感觉数学课要好好听噫

真的只有几道题，其他什么都没有哒

BZOJ-2338: [HNOI2011]数矩形

把所有点的连线按照中点和长度排序，只有中点和长度相等的才能构成长方形。

然后就好办辣。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 1600;
int n,cnt=0;
LL ans;
struct Pts
{
    LL x,y;
    Pts() {}
    Pts(LL _,LL __):x(_),y(__){}
    bool operator == (const Pts &xx) const
    {
        return x == xx.x && y == xx.y;
    }
    Pts operator - (const Pts &xx) const
    {
        return Pts(x-xx.x,y-xx.y);
    }
    LL operator * (const Pts &xx) const
    {
        return x*xx.y-xx.x*y;
    }
}points[NN];
struct L
{
    LL len;
    Pts *p1,*p2;
    Pts mid;
}lines[NN*NN>>1];
bool cmp(L xx,L yy)
{
    if (xx.len == yy.len)
    {
        if (xx.mid.x == yy.mid.x) return xx.mid.y<yy.mid.y;
        return xx.mid.y < yy.mid.y;
    }
    return xx.len < yy.len;
}
LL A_LL(LL xx) { return xx<0ll?-xx:xx; }
LL sqr(LL xx) { return xx*xx; }
LL Dis(const Pts &p1,const Pts &p2)
{
    return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&points[i].x,&points[i].y);
        for (int j=1;j<i;++j)
        {
            lines[++cnt].len = Dis(points[i],points[j]);
            lines[cnt].p1 = &points[i], lines[cnt].p2 = &points[j];
            lines[cnt].mid = Pts(points[i].x+points[j].x,points[i].y+points[j].y);
        }
    }
    sort(lines+1,lines+1+cnt,cmp);
    for (int i=1;i<=cnt;++i)
    {
        for (int j=i-1;j && lines[i].len == lines[j].len && lines[i].mid == lines[j].mid;--j)
            ans = max(ans, A_LL(((*lines[i].p1)-(*lines[j].p1))*((*lines[i].p1)-(*lines[j].p2))));
    }
    printf("%lld\n",ans);
    return 0;
}

BZOJ-1043: [HAOI2008]下落的圆盘

直接考虑每个圆在后面的圆砸完以后还剩下多少就可以了

相关只是都是数学书必修&选修&老师课上的内容啦

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define pi acos(-1)
using namespace std;

const int NN = 1005;

int n,top;
double ans,x[NN],y[NN],r[NN];
struct Line
{
	double l,r;
}a[NN];
bool cmp(Line xx,Line yy) { return xx.l<yy.l; }

inline double sqr(double xx) { return xx*xx; }
inline double Dis(int xx,int yy) { return sqrt(sqr(x[xx]-x[yy])+sqr(y[xx]-y[yy])); }
bool Check(int xx,int yy)
{
	if (r[xx] >= r[yy] + Dis(xx,yy)) return 1; else return 0;
}
void Ins(int xx,int yy)
{
	double d,tmp,st,l;
	d = Dis(xx,yy);
	tmp = (sqr(r[xx])-sqr(r[yy])+sqr(d))/(2.0*d);
	st = atan2((x[xx]-x[yy]),(y[xx]-y[yy]));
	l = acos(tmp/r[xx]);
	a[++top].l = st-l, a[top].r = st+l;
}


double Cal(int xx)
{
	for (int i=xx+1;i<=n;++i) if (Check(i,xx)) return 0;
	top = 0;
	for (int i=xx+1;i<=n;++i) if (!Check(xx,i) && r[xx]+r[i] >= Dis(xx,i)) Ins(xx,i);
	double tmp = 0, now = 0;
	for (int i=1;i<=top;++i)
	{
		if (a[i].l < 0) a[i].l += 2.0*pi;
		if (a[i].r < 0) a[i].r += 2.0*pi;
		if (a[i].l > a[i].r)
		{
			a[++top].l = 0, a[top].r = a[i].r, a[i].r = 2.0*pi;
		}
	}
	sort(a+1,a+top+1,cmp);
	for (int i=1;i<=top;++i)
	if (a[i].l > now) tmp += a[i].l - now, now = a[i].r;
		else now = max(now,a[i].r);
	tmp += 2.0*pi-now;
	return tmp * r[xx];
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);
	for (int i=1;i<=n;++i) ans += Cal(i);
	printf("%.3lf\n",ans);
	return 0;
}

BZOJ-1074: [SCOI2007]折纸origami

找到可能的点，然后一一判断折回来符不符合就可以了

#include <bits/stdc++.h>
using namespace std;
 
const double eps = 1e-6;
const int INF = 1<<29;
struct Point
{
    double x,y;
    inline friend bool operator == (Point xx,Point yy)
    {
        return fabs(xx.x-yy.x)<eps && fabs(xx.y-yy.y)<eps;
    }
};
const Point Wr=(Point){-INF,-INF},Sg=(Point){INF,INF};
struct Line
{
    Point st,en;
};
int n,m,ans;
Line a[10001];
inline double Cross(Point a,Point b)
{
    return a.x*b.y - a.y*b.x;
}
 
Point Rotate(Point xx,Line yy)
{
    Point tx,ty;
    tx.x = xx.x-yy.st.x;
    tx.y = xx.y-yy.st.y;
    ty.x = yy.en.x-yy.st.x;
    ty.y = yy.en.y-yy.st.y;
    Point res;
    if (Cross(ty,tx) > eps)
    {
        if (fabs(yy.st.x-yy.en.x) < eps) res.x = 2*yy.st.x-xx.x, res.y = xx.y;
        else if (fabs(yy.st.y-yy.en.y) < eps) res.x = xx.x, res.y = 2*yy.st.y-xx.y;
        else
        {
            double k=yy.en.y - yy.st.y, k1;
            k /= yy.en.x - yy.st.x;
            k1 = -1/k;
            double b = yy.en.x*yy.st.y-yy.en.y*yy.st.x, b1;
            b /= yy.en.x - yy.st.x;
            if (fabs(xx.x) < eps) b1 = xx.y;
            else b1 = xx.y-k1*xx.x;
            res.x = (b1-b)/(k-k1), res.y = k*res.x+b;
            res.x *= 2, res.y *= 2;
            res.x -= xx.x, res.y -= xx.y;
        }
        return res;
    }
    if (Cross(ty,tx) < -eps) return Wr;
    return Wr;
}
 
bool Check(Point xx)
{
     return xx.x>eps && xx.x<100-eps && xx.y>eps && xx.y<100-eps;
}
 
void DFS(Point xx,int t)
{
    if (t == 0) { if (Check(xx)) ++ ans; return;}
    Point yy = Rotate(xx,a[t]);
    if (yy == Wr) return;
    else if (yy == Sg) DFS(xx,t-1);
    else DFS(yy,t-1), DFS(xx,t-1);
}
 
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%lf%lf%lf%lf",&a[i].st.x,&a[i].st.y,&a[i].en.x,&a[i].en.y);
    scanf("%d",&m);
    for (int i=1;i<=m;++i)
    {
        Point tp;
        ans = 0;
        scanf("%lf%lf",&tp.x,&tp.y);
        DFS(tp,n);
        printf("%d\n",ans);
    }
    return 0;
}

BZOJ-2458: [BeiJing2011]最小三角形

分治。每次分成左右两部分，然后对于中间的用双指针保证距离不大于$\frac{1}{2}ans$，然后统计就可以了。

#include <bits/stdc++.h>
using namespace std;
const int NN = 200200;
const double INF = 1e50;
struct P
{
    int x,y;
}a[NN],num[NN];
int n;
bool cmp(P xx,P yy) { if (xx.x == yy.x) return xx.y<yy.y; else return xx.x<yy.x; }
bool cmpp(P xx,P yy) { if (xx.y == yy.y) return xx.x<yy.x; else return xx.y<yy.y; }
double sqr(int xx) {return 1.0*xx*xx; }
double Dis(P xx,P yy) { return sqrt(sqr(xx.x-yy.x)+sqr(xx.y-yy.y));}
 
inline double Solve(int l,int r)
{
    if (l == r) return INF;
    if (l+1 == r) return INF;
    if (l+2 == r) return Dis(a[l],a[l+1]) + Dis(a[l+1],a[r]) + Dis(a[l],a[r]);
    int mid = (l+r) >> 1;
    double D = min(Solve(l,mid),Solve(mid+1,r)), ans = D, DD = D/2.0;
    int cnt = 0;
    for (int i=l;i<=r;++i)
        if (fabs(a[mid].x-a[i].x) <= DD) num[++cnt] = a[i];
    sort(num+1,num+cnt+1,cmpp);
    for (int i=1;i<cnt-1;++i)
        for (int j=i+1;j<cnt;++j)
        {
            if (num[j].y - num[i].y > DD) break;
            for (int k=j+1;k<=cnt;++k)
            {
                if (num[k].y - num[i].y > DD) break;
                double tmp = Dis(num[i],num[j]) + Dis(num[i],num[k]) + Dis(num[j],num[k]);
                ans = min(ans,tmp);
            }
        }
    return ans;
}
 
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,cmp);
    printf("%.6lf",Solve(1,n));
    return 0;
}