学步园

A - Fractional Lotion

求有多少对(x, y)使得1/x + 1/y = 1/n。

(x+y) / (xy) = 1/n，设x=a*n，y=b*n，那么(a+b)/a*b=1。因为只有2^2 = 2*2，所以a和b两者必然分居2的两侧，即x和y必然一个大于2n，一个小于2n或者都等于2n。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN 10010

int cnt[MAXN];
void init()
{
    for(int i = 1; i < MAXN; i++)
    {
        cnt[i] = 0;
        for(int j = i + 1; j <= 2 * i; j++) if((i * j) % (j - i) == 0) cnt[i]++;
    }
}

int one, n, tot;

int main()
{
//    freopen("A.in", "r", stdin);
    init();
    while(scanf("%d/%d", &one, &n) == 2)
    {
        printf("%d\n", cnt[n]);
    }
    return 0;
}

D - Fence Orthogonality（最小周长外接矩形）

和UVa 12307类似，题解在这里。

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 10010
#define eps 1e-10

template <class T>
inline int RD(T &x)
{
    x = 0;
    char ch = getchar();
    while(!isdigit(ch)) { ch = getchar(); if(ch == EOF) return 0; }
    while(isdigit(ch)) { x *= 10; x += ch - '0'; ch = getchar(); }
    return 1;
}

//const double pi = acos(-1.0);
inline double sig(double x) { return (x > eps) - (x < -eps); };

typedef struct Point
{
        double x, y;
        Point() {}
        Point(double _x, double _y):
                x(_x), y(_y) {}
        bool operator <(const Point &argu) const { return sig(x - argu.x) == 0 ? y < argu.y : x < argu.x; }
        double dis(const Point &argu) const { return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y)); }
        double dis2(const Point &argu) const { return (x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y); }
        double operator ^(const Point &argu) const { return x * argu.y - y * argu.x; }
        double operator *(const Point &argu) const { return x * argu.x + y * argu.y; }
        Point operator -(const Point &argu) const { return Point(x - argu.x, y - argu.y); }
        double len2() const { return x * x + y * y; }
        double len() const { return sqrt(x * x + y * y); }
        void in() { scanf("%lf%lf", &x, &y); }
        void out() { printf("%.3lf %.3lf\n", x, y); }
}Vector;

inline double Cross(const Point &o, const Point &a, const Point &b) { return (a - o) ^ (b - o); }

int ConvexHull(Point p[], Point ch[], int n)
{
    sort(p, p + n);
    int top = 0;
    for(int i = 0; i < n; i++)
    {
        while(top > 1 && Cross(ch[top - 2], ch[top - 1], p[i]) <= 0) top--;
        ch[top++] = p[i];
    }
    int t = top;
    for(int i = n - 2; i >= 0; i--)
    {
        while(top > t && Cross(ch[top - 2], ch[top - 1], p[i]) <= 0) top--;
        ch[top++] = p[i];
    }
    top--;
    return top;
}

void RotatingCalipers(Point p[], int n, double &minp)
{
    int t = 1, l = 1, r = 1;
    minp = 1e15;
    for(int i = 0; i < n; i++)
    {
        //枚举边(p[i], p[i+1])
        while(sig((p[i + 1] - p[i]) ^ (p[t + 1] - p[t])) > 0) t = (t + 1) % n; //找出最高点
        while(sig((p[i + 1] - p[i]) * (p[r + 1] - p[r])) > 0) r = (r + 1) % n; //找出最右点
        if(i == 0) l = (r + 1) % n; //初始化最左点
        while(sig((p[i + 1] - p[i]) * (p[l + 1] - p[l])) < 0) l = (l + 1) % n; //找出最左点
        double d = p[i + 1].dis(p[i]);
        double h = ((p[i + 1] - p[i]) ^ (p[t] - p[i])) / d; //三角形高
        double w = ((p[i + 1] - p[i]) * (p[r] - p[l])) / d; //投影
        minp = min(minp, 2 * (h + w));
    }
}

Point pp[MAXN], ch[MAXN];
int n, c;
double minp;

void solve()
{
    c = ConvexHull(pp, ch, n); ch[c] = ch[0];
    RotatingCalipers(ch, c, minp);
    printf("%.10lf\n", minp);
}

int main()
{
//    freopen("D.in", "r", stdin);

    while(RD(n))
    {
        for(int i = 0; i < n; i++) RD(pp[i].x), RD(pp[i].y);
        solve();
    }
    return 0;
}