@ivorysi 2018-01-02T08:38:08.000000Z 字数 67224 阅读 986

计算几何学习笔记

笔记

平面向量

$(x,y)$

加(减)法

$(x_1+x_2,y_1+y_2)$

点乘

$a=(x_1,y_1)$
$b=(x_2,y_2)$
$x_1*x_2+y_1*y_2$
等于 $|a|*|b|*cos(a,b)$
$|a|$ 表示a的模长

叉乘

$a=(x_1,y_1)$
$b=(x_2,y_2)$
$x_1*y_2-x_2*y_1$
等于 $|a|*|b|*sin(a,b)$
$|a|$ 表示a的模长
这表示它们构成的平行四边形的有向面积
叉乘如果为正表示逆时针，负为顺时针
简称逆正负顺

三角函数

弧长的半径所对的角是一弧度
cosπ=cos 180°=-1

判断一个点是否在多边形内

ZOJ 1081 Points Within

Several drawing applications allow us to draw polygons and almost all of them allow us to fill them with some color. The task of filling a polygon reduces to knowing which points are inside it, so programmers have to colour only those points.
You're expected to write a program which tells us if a given point lies inside a given polygon described by the coordinates of its vertices. You can assume that if a point is in the border of the polygon, then it is in fact inside the polygon.

Input Format

The input file may contain several instances of the problem. Each instance consists of: (i) one line containing integers N, 0 < N < 100 and M, respectively the number of vertices of the polygon and the number of points to be tested. (ii) N lines, each containing a pair of integers describing the coordinates of the polygon's vertices; (iii) M lines, each containing a pair of integer coordinates of the points which will be tested for "withinness" in the polygon.
You may assume that: the vertices are all distinct; consecutive vertices in the input are adjacent in the polygon; the last vertex is adjacent to the first one; and the resulting polygon is simple, that is, every vertex is incident with exactly two edges and two edges only intersect at their common endpoint. The last instance is followed by a line with a 0 (zero).

Output Format

For the ith instance in the input, you have to write one line in the output with the phrase "Problem i:", followed by several lines, one for each point tested, in the order they appear in the input. Each of these lines should read "Within" or "Outside", depending on the outcome of the test. The output of two consecutive instances should be separated by a blank line.

Sample Input

3 1
0 0
0 5
5 0
10 2
3 2
4 4
3 1
1 2
1 3
2 2
0

Sample Output

Problem 1:
Outside
Problem 2:
Outside
Within

题解

过点P做一条平行于x轴的射线
与多边形交点为奇数则为在多边形内
我们先判断这个点在不在多边形的边上，在的话直接返回
注意射线有可能交在线段的端点上，我们强制要求射线交在靠上的端点是交上，交在靠下的端点不算，如果正好三点共线，那么这条线段不会被统计

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 105
//#define ivorysi
using namespace std;
typedef long long ll;
struct Point {
    int x,y;
    Point() {};
    Point(int _x,int _y) {
        x=_x;y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend int operator * (const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
    friend int dot(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }
};
bool check(Point l,Point z,Point s){
    if((l-s)*(z-s)!=0) return false;
    return dot((l-s),(z-s))<=0;
}
int n,m;
struct polygon {
    Point p[MAXN];
    bool inner(const Point &s) {
        int cnt=0;
        siji(i,1,n) {
            if(check(p[i],p[i+1],s)) return true;
            int d1=p[i].y-s.y,d2=p[i+1].y-s.y;
            int delta=(p[i]-s)*(p[i+1]-s);
            if((delta>=0 && d1>=0 && d2<0) || (delta<=0 && d1<0 && d2>=0))
                ++cnt;
        }
        return cnt&1;
    }
}L;
void solve() {
    int t=0;
    while(1) {
        ++t;
        scanf("%d%d",&n,&m);
        if(!n) break;
        if(t!=1) putchar('\n');
        printf("Problem %d:\n",t);
        int x,y;
        siji(i,1,n) {
            scanf("%d%d",&x,&y);
            L.p[i]=Point(x,y);
        }
        L.p[n+1]=L.p[1];
        siji(i,1,m) {
            scanf("%d%d",&x,&y);
            if(L.inner(Point(x,y))) {
                puts("Within");
            }
            else {
                puts("Outside");
            }
        }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0; 
}

解析几何

POJ 1269 Intersecting Lines

Description

We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.

Input

The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).

Output

There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read "END OF OUTPUT".

Sample Input

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

Sample Output

INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT

题解

这是道初中题啊……
然而%.2lf会WA而%.2f会AC
mengbier

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 105
#define esp 1e-6
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    double x,y;
}poi[6];
int n;
bool dcmp(double a,double b) {
    return fabs(a-b)<=esp;
}
void solve() {
    puts("INTERSECTING LINES OUTPUT");
    scanf("%d",&n);
    siji(i,1,n) {
        siji(j,1,4) {
            scanf("%lf%lf",&poi[j].x,&poi[j].y);
        }
        double k1,k2,b1,b2;
        if(dcmp(poi[2].x,poi[1].x) && dcmp(poi[3].x,poi[4].x)) {
            if(dcmp(poi[2].x,poi[3].x)) {
                puts("LINE");
            }
            else puts("NONE");
            continue;
        }
        else if(dcmp(poi[2].x,poi[1].x)){
            k2=(poi[4].y-poi[3].y)/(poi[4].x-poi[3].x);
            b2=poi[3].y-k2*poi[3].x;
            double x=poi[1].x;
            double y=k2*x+b2;
            printf("POINT %.2f %.2f\n",x,y);
            continue;
        }
        else if(dcmp(poi[3].x,poi[4].x)) {
            k1=(poi[2].y-poi[1].y)/(poi[2].x-poi[1].x);
            b1=poi[1].y-k1*poi[1].x;
            double x=poi[3].x;
            double y=k1*x+b1;
            printf("POINT %.2f %.2f\n",x,y);
            continue;
        }
        k1=(poi[2].y-poi[1].y)/(poi[2].x-poi[1].x);
        b1=poi[1].y-k1*poi[1].x;
        k2=(poi[4].y-poi[3].y)/(poi[4].x-poi[3].x);
        b2=poi[3].y-k2*poi[3].x;
        if(dcmp(k1,k2)) {
            if(dcmp(b1,b2)) {
                puts("LINE");
            }
            else {
                puts("NONE");
            }
        }
        else {
            double x=(b2-b1)/(k1-k2);
            double y=k1*x+b1;
            printf("POINT %.2f %.2f\n",x,y);
        }
    }
    puts("END OF OUTPUT");
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0; 
}

计算几何版本

点A到直线CD距离为d1，点B到直线CD距离为d2（带方向）
向量OP=向量OA+向量AB×d1/(d1-d2)

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
};
struct line{
    Point a,b;
    line() {}
    line(double x1,double y1,double x2,double y2) {
    a=Point(x1,y1);
    b=Point(x2,y2);
    }
}L1,L2;
int n;
bool check(line l,line z){
    double res=(l.a-l.b)*(z.a-z.b);
    return dcmp(res,0.0);
}
double dist(Point s,line z) {
    Point k=z.b-z.a;
    return (s-z.a)*k/k.norm();
}
void solve() {
    puts("INTERSECTING LINES OUTPUT");
    scanf("%d",&n);
    siji(i,1,n) {
    double x1,y1,x2,y2;
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    L1=line(x1,y1,x2,y2);
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    L2=line(x1,y1,x2,y2);
    double d1=dist(L1.a,L2);
    double d2=dist(L1.b,L2);
    if(check(L1,L2)) {
        if(dcmp(d1,0.0)) {
        puts("LINE");
        continue;
        }
        else {
        puts("NONE");
        continue;
        }
    }
    double k=d1/(d1-d2);
    Point ans=L1.a+(L1.b-L1.a)*k;
    printf("POINT %.2f %.2f\n",ans.x,ans.y);
    }
    puts("END OF OUTPUT");
}
int T;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

凸包面积

我们按照逆时针的话结果是正的，否则结果是负的
对于每一条边求一个三角形的有向面积，最后求得就是多边形面积
很神奇

POJ 3907 Build Your Home

Description

Mr. Tenant is going to buy a new house. In fact, he is going to buy a piece of land and build his new house on it. In order to decide which piece of land to buy, Mr. Tenant needs a program which will give a score to each piece. Each candidate piece of land is a polygonal shape (not necessarily convex), and Mr. Tenant wonders what the best score is. Among possible scores, he considered the number of vertices, sum of angles, minimum number of required guards, and so forth. Finally, Mr. Tenant decided that the best score for a piece of land would simply be its area. Your task is to write the desired scoring program.

Input

The input file consists of multiple pieces of land. Each piece is a simple polygon (that is, a polygon which does not intersect itself). A polygon description starts with a positive integer number k, followed by k vertices, where each vertex consists of two coordinates (floating-point numbers): x and y. Naturally, the last vertex is connected by an edge to the first vertex. Note that each polygon can be ordered either clockwise or counterclockwise. The input ends with a “0” (the number zero).

Output

For each piece of land, the output should consist of exactly one line containing the score of that piece, rounded to the nearest integer number. (Halves should be rounded up, but Mr. Tenant never faced such cases.)

Sample Input

1 123.45 67.890
3 0.001 0 1.999 0 0 2
5 10 10 10 12 11 11 12 12 12.0 10.0
0

Sample Output

0
2
3

Hint

The scoring program has to handle well degenerate cases, such as, polygons with only one or two vertices.

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-6
//#define ivorysi
using namespace std;
typedef long long ll;
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x=_x;y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
    friend double dot(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }
};
int n;
struct polygon {
    Point p[MAXN];
    double Area() {
        double res=0.0;
        siji(i,1,n) {
            res+=p[i]*p[i+1]/2;
        }
        return fabs(res);
    }
}L;
void solve() {
    while(scanf("%d",&n)!=EOF) {
        if(n==0) break;
        double x,y;
        siji(i,1,n) {
            scanf("%lf%lf",&x,&y);
            L.p[i]=Point(x,y);
        }
        if(n<=2) {
            puts("0");
            continue;
        }
        L.p[n+1]=L.p[1];
        double ans=L.Area();
        printf("%d\n",(int)(ans+0.5));
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0; 
}

POJ 2318 TOYS

Description

Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.
John's parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.
For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

Input

The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.

Output

The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

Hint

As the example illustrates, toys that fall on the boundary of the box are "in" the box.

题解

这道题也是判断点在不在多边形内
但是我们需要二分……不然会T

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct Point {
    ll x,y;
    Point() {}
    Point(ll _x,ll _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend ll operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend ll dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
}toy[10005];
bool check(Point l,Point z,Point s) {
    if((l-s)*(z-s)!=0) return false;
    return dot(l-s,z-s)<=0;
}
struct polygen {
    Point p[6];
    int inner(const Point &b) {
    int cnt=0;
    siji(i,1,4) {
        if(check(p[i],p[i+1],b)) return 1;
        ll d1=p[i].y-b.y,d2=p[i+1].y-b.y;
        ll delta=(p[i]-b)*(p[i+1]-b);
        if((delta>=0 && d1>=0 && d2<0) ||(delta<=0 && d1<0 && d2>=0)) ++cnt;
    }
    return cnt;
    }
}L[10005];
ll upper[20005],lower[20005];
ll x1,x2,y1,y2;
int ans[20005];
int n,m;
void solve() {
    int id=1,last;
    sort(toy+1,toy+m+1);
    memset(ans,0,sizeof(ans));
    siji(i,0,n) {
    L[i].p[1]=Point(upper[i],y1);
    L[i].p[2]=Point(upper[i+1],y1);
    L[i].p[3]=Point(lower[i+1],y2);
    L[i].p[4]=Point(lower[i],y2);
    L[i].p[5]=L[i].p[1];
    }
    siji(i,1,m) {
    int l=0,r=n;
    while(l<=r) {
        int mid=(l+r)>>1;
        int x=L[mid].inner(toy[i]);
        if(x&1) {
        ans[mid]++;
        break;
        }
        if(x>0) l=mid+1;
        else r=mid;
    }
    }
    siji(i,0,n) {
    printf("%d: %d\n",i,ans[i]);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    int t=0;
    while(scanf("%d",&n)!=EOF) {
    ++t;
    if(t!=1) puts("");
    if(!n) break;
    scanf("%d%lld%lld%lld%lld",&m,&x1,&y1,&x2,&y2);
    ll x,y;
    siji(i,1,n) {
        scanf("%lld%lld",&upper[i],&lower[i]);
    }
    siji(i,1,m) {
        scanf("%lld%lld",&x,&y);
        toy[i]=Point(x,y);
    }
    upper[0]=x1;lower[0]=x1;
    upper[n+1]=x2;lower[n+1]=x2;
    solve();
    }
    return 0;
}

判断直线和线段有交点

找到直线上的一个向量，看它到线段的两个端点旋转的方向是不是相反
也就是，直线上的向量分别与线段端点到向量起点的向量叉乘，叉乘符号是不是相反

　POJ 3304 Segments

Description

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1 y1 x2 y2 follow, in which (x1, y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments.

Output

For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10-8.

Sample Input

3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0

Sample Output

Yes!
Yes!
No!

题解

这道题说的是投影有公共点，那么公共部分的左右端点一定对应着某两条线段的端点，然后我们枚举所有端点然后连接，这个连接出来的直线一定会穿过所有的线段

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
};
struct line{
    Point a,b;
}seg[105];
int n;
bool check(Point l,Point z) {
    if(l==z) return 0;
    siji(i,1,n) {
    if(((l-seg[i].a)*(l-z)) *((l-seg[i].b)*(l-z)) > esp) return 0;
    }
    return 1;
}
void solve() {
    scanf("%d",&n);
    double x1,y1,x2,y2;
    siji(i,1,n) {
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    seg[i].a=Point(x1,y1);
    seg[i].b=Point(x2,y2);
    }
    if(n<3) {
    puts("Yes!");
    return;
    }
    siji(i,1,n) {
    siji(j,i+1,n) {
        if(check(seg[i].a,seg[j].b) ||
           check(seg[i].b,seg[j].a) ||
           check(seg[i].a,seg[j].a) ||
           check(seg[i].b,seg[j].b)
        ) {
        puts("Yes!");
        return;
        }
    }
    }
    puts("No!");
}
int T;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--) {
    solve();
    }
    return 0;
}

判断两个线段是否相交

我们对于每条线段，看看另一个线段两个端点是不是分局它的两侧
也就是两次直线和线段是否相交

POJ 1066 Treasure Hunt

Description

Archeologists from the Antiquities and Curios Museum (ACM) have flown to Egypt to examine the great pyramid of Key-Ops. Using state-of-the-art technology they are able to determine that the lower floor of the pyramid is constructed from a series of straightline walls, which intersect to form numerous enclosed chambers. Currently, no doors exist to allow access to any chamber. This state-of-the-art technology has also pinpointed the location of the treasure room. What these dedicated (and greedy) archeologists want to do is blast doors through the walls to get to the treasure room. However, to minimize the damage to the artwork in the intervening chambers (and stay under their government grant for dynamite) they want to blast through the minimum number of doors. For structural integrity purposes, doors should only be blasted at the midpoint of the wall of the room being entered. You are to write a program which determines this minimum number of doors.
An example is shown below:

Input

The input will consist of one case. The first line will be an integer n (0 <= n <= 30) specifying number of interior walls, followed by n lines containing integer endpoints of each wall x1 y1 x2 y2 . The 4 enclosing walls of the pyramid have fixed endpoints at (0,0); (0,100); (100,100) and (100,0) and are not included in the list of walls. The interior walls always span from one exterior wall to another exterior wall and are arranged such that no more than two walls intersect at any point. You may assume that no two given walls coincide. After the listing of the interior walls there will be one final line containing the floating point coordinates of the treasure in the treasure room (guaranteed not to lie on a wall).

Output

Print a single line listing the minimum number of doors which need to be created, in the format shown below.

Sample Input

7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4

Sample Output

Number of doors = 2

题解

枚举墙上的每个端点然后判断是否相交
这里如果端点在线段上不算相交
所以我们要判断叉积是不是0

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
bool dgreater(double x,double y) {
    if(dcmp(x,y)) return 1;
    return x>y;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
};
struct line{
    Point a,b;
}seg[105];
int n;
int ans;
bool check(line l,line z) {
    if(l.b==z.a || l.b==z.b) return 0;
    siji(i,1,n) {
    if(dgreater(((l.a-l.b)*(l.a-z.a)) * ((l.a-l.b)*(l.a-z.b)),0.0)) return 0;
    if(dgreater(((z.a-z.b)*(z.a-l.a)) * ((z.a-z.b)*(z.a-l.b)),0.0)) return 0;
    }
    return 1;
}
void solve() {
    scanf("%d",&n);
    double x1,y1,x2,y2;
    siji(i,1,n) {
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    seg[i].a=Point(x1,y1);
    seg[i].b=Point(x2,y2);
    }
    ans=n;
    double x,y;
    scanf("%lf%lf",&x,&y);
    siji(i,1,4) seg[n+i].a=Point(x,y);
    if(n==0) {
    puts("Number of doors = 1");
    return;
    }
    siji(i,0,100) {
    int tmp[5];
    memset(tmp,0,sizeof(tmp));
    seg[n+1].b=Point(0.0,(double)i);
    seg[n+2].b=Point(100.0,(double)i);
    seg[n+3].b=Point((double)i,0.0);
    seg[n+4].b=Point((double)i,100.0);
    siji(j,1,n) {
        siji(k,1,4) {
        if(check(seg[j],seg[n+k])) ++tmp[k];
        }
    }
    siji(j,1,4) {
        ans=min(ans,tmp[j]);
    }
    }
    printf("Number of doors = %d\n",ans+1);
}
int T;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ 1039 Pipe

Description

The GX Light Pipeline Company started to prepare bent pipes for the new transgalactic light pipeline. During the design phase of the new pipe shape the company ran into the problem of determining how far the light can reach inside each component of the pipe. Note that the material which the pipe is made from is not transparent and not light reflecting.
Each pipe component consists of many straight pipes connected tightly together. For the programming purposes, the company developed the description of each component as a sequence of points [x1; y1], [x2; y2], . . ., [xn; yn], where x1 < x2 < . . . xn . These are the upper points of the pipe contour. The bottom points of the pipe contour consist of points with y-coordinate decreased by 1. To each upper point [xi; yi] there is a corresponding bottom point [xi; (yi)-1] (see picture above). The company wants to find, for each pipe component, the point with maximal x-coordinate that the light will reach. The light is emitted by a segment source with endpoints [x1; (y1)-1] and [x1; y1] (endpoints are emitting light too). Assume that the light is not bent at the pipe bent points and the bent points do not stop the light beam.

Input

The input file contains several blocks each describing one pipe component. Each block starts with the number of bent points 2 <= n <= 20 on separate line. Each of the next n lines contains a pair of real values xi, yi separated by space. The last block is denoted with n = 0.

Output

The output file contains lines corresponding to blocks in input file. To each block in the input file there is one line in the output file. Each such line contains either a real value, written with precision of two decimal places, or the message Through all the pipe.. The real value is the desired maximal x-coordinate of the point where the light can reach from the source for corresponding pipe component. If this value equals to xn, then the message Through all the pipe. will appear in the output file.

Sample Input

4
0 1
2 2
4 1
6 4
6
0 1
2 -0.6
5 -4.45
7 -5.57
12 -10.8
17 -16.55
0

Sample Output

4.67
Through all the pipe.

题解

我们一条线段如果最优的话一定会经过一个上端点和一个下端点
比较烦人的地方是我们可能还会有一些光线可能超过某个端点射出去了
我们就需要用两个端点之间的线段来限制这条光线
然后这样就可以过了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
}poi[105];
struct line{
    Point a,b;
    line() {}
    line(double x1,double y1,double x2,double y2) {
    a=Point(x1,y1);
    b=Point(x2,y2);
    }
    line(Point _a,Point _b) {
    a=_a;b=_b;
    }
}seg;
int n;
bool check(Point a,Point b,line l) {
    double cross1=(l.b-l.a)*(a-l.a);
    double cross2=(l.b-l.a)*(b-l.a);
    if(dcmp(cross1,0) && dcmp(cross2,0)) return 1;
    return cross1*cross2 < 0.0;
}
bool check(Point s,line l){
    return dcmp((l.a-l.b)*(s-l.b),0.0);
}
double dist(Point s,line z){
    Point k=z.b-z.a;
    return (s-z.a)*k/k.norm();
}
double lengthen(line z) {
    int p=2;
    if((!check(poi[1],poi[1+n],z))
       && (!check(poi[1],z))
       && (!check(poi[1+n],z))) return poi[1].x;
    while(p<=n) {
    if(poi[p].x>z.b.x) break;
    if(check(poi[p-1],poi[p],z) || check(poi[p-1+n],poi[p+n],z)) return poi[1].x;
    if((!check(poi[p],poi[p+n],z))
       && (!check(poi[p],z))
       && (!check(poi[p+n],z))) return poi[1].x;
    ++p;
    }
    double res=z.b.x;
    while(p<=n) {
    if(check(poi[p-1],poi[p],z) || check(poi[p-1+n],poi[p+n],z)) {
        double tmp=poi[n].x,d1,d2;
        Point pos;
        if(check(poi[p-1],poi[p],z)) {
        d1=dist(poi[p-1],z);
        d2=dist(poi[p],z);
        if(dcmp(d1-d2,0.0)) {tmp=min(tmp,poi[p-1].x);}
        else {
            pos=poi[p-1]+(poi[p]-poi[p-1])*(d1/(d1-d2));
            tmp=min(tmp,pos.x);
        }
        }
        if(check(poi[p-1+n],poi[p+n],z)) {
        d1=dist(poi[p-1+n],z);
        d2=dist(poi[p+n],z);
        if(dcmp(d1-d2,0.0)) {
            tmp=min(tmp,poi[p+n-1].x);
        }
        else {
            pos=poi[p-1+n]+(poi[p+n]-poi[p-1+n])*(d1/(d1-d2));
            tmp=min(tmp,pos.x);
        }
        }
        res=tmp;
        break;
    }
    if((!check(poi[p],poi[p+n],z))
       && (!check(poi[p],z))
       && (!check(poi[p+n],z))) break;
    res=poi[p].x;
    ++p;
    }
    return res;
}
void solve() {
    siji(i,1,n) {
    double x,y;
    scanf("%lf%lf",&x,&y);
    poi[i]=Point(x,y);
    }
    siji(i,n+1,2*n) {
    poi[i]=poi[i-n];
    poi[i].y-=1.0;
    }
    double ans=poi[1].x;
    siji(i,1,n) {
    siji(j,i+1,n) {
        if(i==j) continue;
        seg=line(poi[i],poi[j+n]);
        double x=lengthen(seg);
        ans=max(ans,x);
        seg=line(poi[i+n],poi[j]);
        x=lengthen(seg);
        ans=max(ans,x);
    }
    }
    if(dcmp(ans,poi[n].x)) {
    puts("Through all the pipe.");
    }
    else {
    printf("%.2f\n",ans);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&n)!=EOF) {
    if(!n) break;
    solve();
    }
    return 0;
}

POJ 2074 Line of Sight

Description

An architect is very proud of his new home and wants to be sure it can be seen by people passing by his property line along the street. The property contains various trees, shrubs, hedges, and other obstructions that may block the view. For the purpose of this problem, model the house, property line, and obstructions as straight lines parallel to the x axis:
To satisfy the architect's need to know how visible the house is, you must write a program that accepts as input the locations of the house, property line, and surrounding obstructions and calculates the longest continuous portion of the property line from which the entire house can be seen, with no part blocked by any obstruction.

Input

Because each object is a line, it is represented in the input file with a left and right x coordinate followed by a single y coordinate:
< x1 > < x2 > < y >
Where x1, x2, and y are non-negative real numbers. x1 < x2
An input file can describe the architecture and landscape of multiple houses. For each house, the first line will have the coordinates of the house. The second line will contain the coordinates of the property line. The third line will have a single integer that represents the number of obstructions, and the following lines will have the coordinates of the obstructions, one per line.
Following the final house, a line "0 0 0" will end the file.
For each house, the house will be above the property line (house y > property line y). No obstruction will overlap with the house or property line, e.g. if obstacle y = house y, you are guaranteed the entire range obstacle[x1, x2] does not intersect with house[x1, x2].

Output

For each house, your program should print a line containing the length of the longest continuous segment of the property line from which the entire house can be to a precision of 2 decimal places. If there is no section of the property line where the entire house can be seen, print "No View".

Sample Input

2 6 6
0 15 0
3
1 2 1
3 4 1
12 13 1
1 5 5
0 10 0
1
0 15 1
0 0 0

Sample Output

8.80
No View

题解

这道题需要我们转换思路
我们首先容易想到让两个线射向一个缺口，但是这样会很麻烦
我们转化成房子是一个光源，它们在街道上有一个投影
这就是很多条线段，然后求这些线段在街道上没有覆盖的最长的长度

为什么G++一直WA C++就秒过啊！！！！

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
};
struct line {
    Point a,b;
}obj[10005],house,proper;
struct node {
    double s,t;
    bool operator < (const node &rhs)const {
    return s<rhs.s;
    }
}shadow[10005];
double dist(Point z,line l) {
    Point k=l.b-l.a;
    return (z-l.a)*k/k.norm();
}
Point cross_point(Point l,Point z,line s) {
    double d1=dist(l,s),d2=dist(z,s);
    Point res=l+(z-l)*(d1/(d1-d2));
    return res;
}
int n,tot;
bool solve() {
    double x1,x2,y;
    scanf("%lf%lf%lf",&x1,&x2,&y);
    if(dcmp(x1,0.0) && dcmp(x2,0.0) && dcmp(y,0.0)) return false;
    house.a=Point(x1,y);house.b=Point(x2,y);
    scanf("%lf%lf%lf",&x1,&x2,&y);
    proper.a=Point(x1,y);proper.b=Point(x2,y);
    scanf("%d",&n);
    tot=0;
    siji(i,1,n) {
    scanf("%lf%lf%lf",&x1,&x2,&y);
    if(y>=house.a.y || y<=proper.a.y) continue;
    obj[++tot].a=Point(x1,y);
    obj[tot].b=Point(x2,y);
    }
    siji(i,1,tot) {
    Point k=cross_point(house.b,obj[i].a,proper);
    shadow[i].s=k.x;
        k=cross_point(house.a,obj[i].b,proper);
    shadow[i].t=k.x;
    }
    double ans=0.0;
    double Lmax=proper.a.x;
    sort(shadow+1,shadow+tot+1);
    siji(i,1,tot) {
    if(shadow[i].s>=proper.b.x) break;
    if(shadow[i].s>Lmax) {
        ans=max(shadow[i].s-Lmax,ans);
    }
    Lmax=max(Lmax,shadow[i].t);
    }
    ans=max(ans,proper.b.x-Lmax);
    if(dcmp(ans,0.00)) {
    puts("No View");
    }
    else {
    printf("%.2lf\n",ans);
    }
    return true;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(1) {
    if(!solve()) break;
    }
    return 0;
}

POJ 1035 Intervals

Description

In the ceiling in the basement of a newly open developers building a light source has been installed. Unfortunately, the material used to cover the floor is very sensitive to light. It turned out that its expected life time is decreasing dramatically. To avoid this, authorities have decided to protect light sensitive areas from strong light by covering them. The solution was not very easy because, as it is common, in the basement there are different pipelines under the ceiling and the authorities want to install the covers just on those parts of the floor that are not shielded from the light by pipes. To cope with the situation, the first decision was to simplify the real situation and, instead of solving the problem in 3D space, to construct a 2D model first.
Within this model, the x-axis has been aligned with the level of the floor. The light is considered to be a point light source with integer co-ordinates [bx,by]. The pipes are represented by circles. The center of the circle i has the integer co-ordinates [cxi,cyi] and an integer radius ri. As pipes are made from solid material, circles cannot overlap. Pipes cannot reflect the light and the light cannot go through the pipes. You have to write a program which will determine the non-overlapping intervals on the x-axis where there is, due to the pipes, no light from the light source.

Input

The input consists of blocks of lines, each of which except the last describes one situation in the basement. The first line of each block contains a positive integer number N < 500 expressing the number of pipes. The second line of the block contains two integers bx and by separated by one space. Each of the next N lines of the block contains integers cxi, cyi and ri, where cyi + ri < by. Integers in individual lines are separated by one space. The last block consists of one line containing n = 0.

Output

The output consists of blocks of lines, corresponding to the blocks in the input(except the last one). One empty line must be put after each block in the output. Each of the individual lines of the blocks in the output will contain two real numbers, the endpoints of the interval where there is no light from the given point light source. The reals are exact to two decimal places and separated by one space. The intervals are sorted according to increasing x-coordinate.

Sample Input

6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
1
300 300
300 150 90
1
300 300
390 150 90
0

Sample Output

0.72 78.86
88.50 133.94
181.04 549.93

75.00 525.00

300.00 862.50

题解

我们不要忘了这样一个事实！！！
我们有计算机！！！
我们可以轻松求出，一个已知斜边和直角边的三角形，任意一个角的度数！！！
然后再套用向量的旋转公式
再用直线的交点
就求出了一条条阴影
这道题就做完了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
}ceiling,cir;
struct line {
    Point a,b;
}flr;
struct node {
    double s,t;
    bool operator < (const node &rhs) const {
    return s<rhs.s;
    }
}seg[100005];
int n,tot;
Point rotate(Point l,Point z,double k) {
    Point s=z-l;
    Point res=l+Point(s.x*cos(k)-s.y*sin(k),s.x*sin(k)+s.y*cos(k));
    return res;
}
double dist(Point z,line l) {
    Point k=l.b-l.a;
    return (z-l.a)*k/k.norm();
}
double dist(Point l,Point z) {
    Point s=z-l;
    return s.norm();
}
Point cross_point(Point l,Point z,line s) {
    double d1=dist(l,s),d2=dist(z,s);
    Point res=l+(z-l)*(d1/(d1-d2));
    return res;
}
void solve() {
    tot=0;
    scanf("%lf%lf",&ceiling.x,&ceiling.y);
    double xc,yc,r;
    siji(i,1,n) {
    scanf("%lf%lf%lf",&xc,&yc,&r);
    cir=Point(xc,yc);
    double d=dist(ceiling,cir);
    double t=asin(r/d);
    Point l=rotate(ceiling,cir,-t);
    Point z=rotate(ceiling,cir,t);
    seg[++tot].s=(cross_point(ceiling,l,flr)).x;
    seg[tot].t=(cross_point(ceiling,z,flr)).x;
    }
    sort(seg+1,seg+tot+1);
    double st=seg[1].s,ed=seg[1].t;
    siji(i,2,tot) {
    if(seg[i].s>ed) {
        printf("%.2f %.2f\n",st,ed);
        st=seg[i].s;
        ed=seg[i].t;
    }
    else {
        ed=max(seg[i].t,ed);
    }
    }
    printf("%.2f %.2f\n",st,ed);
    puts("");
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    flr.a=Point(0.0,0.0);
    flr.b=Point(1.0,0.0);
    int t=0;
    while(scanf("%d",&n)!=EOF) {
    if(n==0) break;
    ++t;
    solve();
    }
    return 0;
}

POJ 3347 Kadj Squares

Description

In this problem, you are given a sequence S1, S2, ..., Sn of squares of different sizes. The sides of the squares are integer numbers. We locate the squares on the positive x-y quarter of the plane, such that their sides make 45 degrees with x and y axes, and one of their vertices are on y=0 line. Let bi be the x coordinates of the bottom vertex of Si. First, put S1 such that its left vertex lies on x=0. Then, put S1, (i > 1) at minimum bi such that
bi > bi-1 and
the interior of Si does not have intersection with the interior of S1...Si-1.
The goal is to find which squares are visible, either entirely or partially, when viewed from above. In the example above, the squares S1, S2, and S4 have this property. More formally, Si is visible from above if it contains a point p, such that no square other than Si intersect the vertical half-line drawn from p upwards.

Input

The input consists of multiple test cases. The first line of each test case is n (1 ≤ n ≤ 50), the number of squares. The second line contains n integers between 1 to 30, where the ith number is the length of the sides of Si. The input is terminated by a line containing a zero number.

Output

For each test case, output a single line containing the index of the visible squares in the input sequence, in ascending order, separated by blank characters.

Sample Input

4
3 5 1 4
3
2 1 2
0

Sample Output

1 2 4
1 3

题解

这道题是道思维题……就是几何题，和计算几何没啥关系
我们把投影长度扩大根号2倍，就可以当做整数处理了
求坐标的时候是1-i-1的坐标下标能延伸到最远的位置
max{t[j]+2*min(s[j],s[i])}
然后将每个方块变成一条投影
找1-i-1向右延伸到最远的位置和i+1到n向左延伸到最远的位置
如果这两个位置之间有空隙那么这个方块就可以被看到
注意一开始向右延伸的初始值是i方块投影的左端点
向左延伸的初始值是i方块投影的右端点

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
}ceiling,cir;
struct line {
    Point a,b;
}flr;
struct node {
    int s,t;
}seg[100005];
int n;
int s[55],t[55],tot;
bool visable[55];
void solve() {
    memset(visable,0,sizeof(visable));
    memset(t,0,sizeof(t));
    siji(i,1,n) {
    scanf("%d",&s[i]);
    }
    t[1]=s[1];
    seg[1].s=0;
    seg[1].t=2*s[1];
    siji(i,2,n) {
    xiaosiji(j,1,i) {
        t[i]=max(t[j]+2*min(s[j],s[i]),t[i]);
    }
    seg[i].s=t[i]-s[i];
    seg[i].t=t[i]+s[i];
    }
    siji(i,1,n) {
    bool flag=1;
    int l=seg[i].t,r=seg[i].s;
    xiaosiji(j,1,i) {
        r=max(seg[j].t,r);
    }
    siji(j,i+1,n) {
        l=min(l,seg[j].s);
    }
    if(l>r) visable[i]=1;
    }
    int tot=0;
    siji(i,1,n) {
    if(visable[i]) {
        ++tot;
    }
    }
    siji(i,1,n) {
        if(visable[i]) {
            --tot;
            printf("%d%c",i," \n"[tot==0]);
        }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&n)!=EOF) {
    if(n==0) break;
    solve();
    }
    return 0;
}

POJ 2826 An Easy Problem?!

Description

It's raining outside. Farmer Johnson's bull Ben wants some rain to water his flowers. Ben nails two wooden boards on the wall of his barn. Shown in the pictures below, the two boards on the wall just look like two segments on the plane, as they have the same width.
Your mission is to calculate how much rain these two boards can collect.

Input

The first line contains the number of test cases.
Each test case consists of 8 integers not exceeding 10,000 by absolute value, x1, y1, x2, y2, x3, y3, x4, y4. (x1, y1), (x2, y2) are the endpoints of one board, and (x3, y3), (x4, y4) are the endpoints of the other one.

Output

For each test case output a single line containing a real number with precision up to two decimal places - the amount of rain collected.

Sample Input

2
0 1 1 0
1 0 2 1

0 1 2 1
1 0 1 2

Sample Output

1.00
0.00

题解

这道题我们一开始先找到这两个线段的交点，如果没有交点那么必然盛不了水
然后在交点的上面找两条线段的端点，然后做一条平行与x轴的直线和看和另一条线段有没有交点
如果有交点，还要看看另一条线段的投影是不是完全覆盖了这条线段
如果投影完全覆盖了另一条线段就是盛不了水
但是这道题还是保持着POJ一贯的坑
我们要把答案还用%.2f然后答案还要加上esp

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
    return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
};
struct line {
    Point a,b;
}L1,L2,para;
struct node {
    double s,t;
}seg1,seg2;
int T;
bool is_cross(line l,line z) {
    double res1=((l.b-l.a)*(z.b-l.a))*((l.b-l.a)*(z.a-l.a));
    double res2=((z.b-z.a)*(l.a-z.a))*((z.b-z.a)*(l.b-z.a));
    return res1<=0.0 && res2<=0.0;
}
double dist(Point z,line l) {
    Point k=l.b-l.a;
    return (z-l.a)*k/k.norm();
}
Point cross_point(line l,line z) {
    double d1=dist(l.a,z);
    double d2=dist(l.b,z);
    if(dcmp(d1,d2)) {
    return Point(-100000000,-1);
    }
    return l.a+(l.b-l.a)*(d1/(d1-d2));
}
void solve() {
    double x1,y1,x2,y2;
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    L1.a=Point(x1,y1);
    L1.b=Point(x2,y2);
    if(y1<y2) {
    swap(L1.a,L1.b);
    }
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    L2.a=Point(x1,y1);
    L2.b=Point(x2,y2);
    if(y1<y2) {
    swap(L2.a,L2.b);
    }
    double ans=0.0;
    if(!is_cross(L1,L2)) {
    puts("0.00");
    return;
    }
    else {
    Point k=cross_point(L1,L2);
    double h;
    if(L1.a.y>k.y) {
        h=L1.a.y;
        para.a=Point(1.0,h);
        para.b=Point(0.0,h);
        Point s=cross_point(para,L2);
        if((!dcmp(s.x,-100000000)) && s.y<=L2.a.y) {
        seg1.s=s.x;seg1.t=L1.a.x;
        seg2.s=s.x;seg2.t=L2.a.x;
        if(seg1.s>seg1.t) swap(seg1.s,seg1.t);
        if(seg2.s>seg2.t) swap(seg2.s,seg2.t);
        if(seg2.s<=seg1.s && seg2.t>=seg1.t) {
            goto fail1;
        }
        ans=max(ans,fabs(s.x-L1.a.x)*(L1.a.y-k.y)*0.5);
        }
    }
        fail1:;
    if(L2.a.y>k.y) {
        h=L2.a.y;
        para.a=Point(1.0,h);
        para.b=Point(0.0,h);
        Point s=cross_point(para,L1);
        if((!dcmp(s.x,-100000000)) && s.y<=L1.a.y) {
        seg1.s=s.x;seg1.t=L2.a.x;
        seg2.s=s.x;seg2.t=L1.a.x;
        if(seg1.s>seg1.t) swap(seg1.s,seg1.t);
        if(seg2.s>seg2.t) swap(seg2.s,seg2.t);
        if(seg2.s<=seg1.s && seg2.t>=seg1.t) {
            goto fail2;
        }
        ans=max(ans,fabs(s.x-L2.a.x)*(L2.a.y-k.y)*0.5);
        }
    }
        fail2:;
    }
    printf("%.2f\n",ans+esp);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--) {
    solve();
    }
    return 0;
}

SGU 253. Theodore Roosevelt

Danger! Sudden attack on Russia! These are Americans "again", but this time they are serious. Giant aircraft-carrier "Theodore Roosevelt" is entering the Baltic Sea. At one o'clock American aircraft launched from the carrier bombed Petrozavodsk.
At three o'clock we detected the location of "Theodore Roosevelt". In a moment Russian fighters Mig-29 took off into the night air to inflict the crushing strike against the carrier. Using top secret military satellite "Raduga-1" we detected the exact region where the carrier was located - the convex polygon. The fighters launched M rockets and ground forces detected the coordinates of their explosions.
You are an indispensable engineer of Russian military forces, and you were waken up by the phone call at four o'clock. They command you to arrive to headquarters for the most important task - detect whether "Theodore Roosevelt" was destroyed or not! You are given all information: the coordinates of vertices of the region polygon and the coordinates of the explosions.
It was computed that at least K rockets should have hit the detected region to destroy the carrier. Commander ordered you to complete the work till five o'clock, so you must hurry.

Input

The first line of input contains three integers N, M and K (3<=N<=10^5, 0<=K<=M<=10^5). The following N lines contain coordinates of polygon vertices in counter-clockwise order. And then last M lines contain coordinates of rockets explosions. Is is guaranteed that all coordinates are integer numbers not exceeding 10^9 by their absolute value.

Output

Output "YES" (without quotes) if "Theodore Roosevelt" was destroyed, or "NO" (without quotes) in the other case.

Sample test(s)

Input

5 4 2
1 -1
1 2
0 4
-1 2
-1 -1
-2 -1
1 -1
0 1
2 3

Output

YES

题解

这道题是一道计算几何题！！！！！！！
然后我一开始想的是分类讨论，把这个凸包分成左右两个边然后二分！！！
然后特别麻烦！！！
我后来翻了翻题解
找到左下角的点，按极角排序，然后二分找到p[1]到这个点的向量顺时针旋转到的第一个点，逆时针旋转到的第一个点
然后看看这三个点构成的三角形是不是囊括了这个点，只要判断这个点和另外三边构成的面积是不是等于左下角的点，二分到的两个点这三个点构成的三角形的面积
再特判一下这个点在不在1到它的边上

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double a,double b) {
    return fabs(a-b)<=esp;
}
struct Point {
    ll x,y;
    Point() {}
    Point(ll _x,ll _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend ll operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend ll dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    ll norm() {
    return x*x+y*y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
}poi;
int n,m,k,T,tot;
Point p[MAXN],tmp[MAXN];
struct line {
    Point a,b;
};
int findleft(int l,int r,Point z) {
    while(l<r) {
    int mid=(l+r)>>1;
    if((z-p[1])*(p[mid]-p[1])>=0) r=mid;
    else l=mid+1;
    }
    return l;
}
int findright(int l,int r,Point z) {
    while(l<r) {
    int mid=(l+r+1)>>1;
    if((z-p[1])*(p[mid]-p[1])<=0) l=mid;
    else r=mid-1;
    }
    return l;
}
ll Area(Point l,Point z,Point s) {
    return abs((s-l)*(s-z));
}
bool is_on_line(line l,Point z) {
    if((l.a-z)*(l.b-z)!=0) return 0;
    return dot(l.a-z,l.b-z)<=0;
}
bool cmp(Point a,Point b) {
    return (a-p[1])*(b-p[1])>0
    || ((a-p[1])*(b-p[1])==0 && (a-p[1]).norm()<(b-p[1]).norm());
}
ll gcd(ll a,ll b) {
    return b==0 ? a:gcd(b,a%b);
}
void solve() {
    scanf("%d%d%d",&n,&m,&k);
    ll x,y;
    int id=0;
    siji(i,1,n) {
    scanf("%lld%lld",&x,&y);
    p[i]=Point(x,y);
    if(id==0) id=i;
    else if(p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y)) {
        id=i;
    }
    }
    if(id!=1) swap(p[1],p[id]);
    sort(p+2,p+n+1,cmp);
    p[n+1]=p[1];
    memcpy(tmp,p,sizeof(p));
    tot=1;
    id=2;
    siji(i,2,n) {
    if((tmp[i]-p[1])*(tmp[i+1]-p[1])!=0) {
        p[++tot]=tmp[i];
    }
    }
    p[++tot]=tmp[n];
    int cnt=0;
    siji(i,1,m) {
    scanf("%lld%lld",&x,&y);
    if(x<p[1].x) continue;
    poi=Point(x,y);
    int t1=findleft(2,tot,poi);
    int t2=findright(2,tot,poi);
    if(t1!=1 && is_on_line((line){p[1],p[t1]},poi)) {
        ++cnt;
    }
    else if(t2!=1 && is_on_line((line){p[1],p[t2]},poi)) {
        ++cnt;
    }
    else if(t2!=t1){
        if(Area(p[1],p[t2],poi)+Area(p[1],p[t1],poi)+Area(p[t1],p[t2],poi)==Area
           (p[1],p[t1],p[t2])) ++cnt;
    }
    }
    if(cnt>=k) {
    puts("YES");
    }
    else {
    puts("NO");
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ 3348 Cows

Description

Your friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Given the locations of some trees, you are to help farmers try to create the largest pasture that is possible. Not all the trees will need to be used.
However, because you will oversee the construction of the pasture yourself, all the farmers want to know is how many cows they can put in the pasture. It is well known that a cow needs at least 50 square metres of pasture to survive.

Input

The first line of input contains a single integer, n (1 ≤ n ≤ 10000), containing the number of trees that grow on the available land. The next n lines contain the integer coordinates of each tree given as two integers x and y separated by one space (where -1000 ≤ x, y ≤ 1000). The integer coordinates correlate exactly to distance in metres (e.g., the distance between coordinate (10; 11) and (11; 11) is one metre).

Output

You are to output a single integer value, the number of cows that can survive on the largest field you can construct using the available trees.

Sample Input

4
0 0
0 101
75 0
75 101

Sample Output

151

题解

这个要卷包裹算法
我们找到左下角的点，剩下的按极角排序
然后放进队列里，每次把队尾的两个点拿出来比较一下和新加入的点是不是逆时针旋转
如果是逆时针旋转，那么就可以扩大凸包，队尾的点出队

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double a,double b) {
    return fabs(a-b)<=esp;
}
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend int operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend int dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    double norm() {
    return x*x+y*y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
};
Point p[MAXN];
Point que[MAXN];
int n,id,ql;
bool cmp(Point a,Point b) {
    int delta=(a-p[1])*(b-p[1]);
    if(delta!=0) return delta>0;
    return (a-p[1]).norm()<(b-p[1]).norm();
}
int Area() {
    int res=0;
    siji(i,1,ql) {
    res+=que[i]*que[i+1];
    }
    return res/2;
}
void solve() {
    scanf("%d",&n);
    int x,y;
    id=1;
    siji(i,1,n) {
    scanf("%d%d",&x,&y);
    p[i]=Point(x,y);
    if(x<p[id].x || (x==p[id].x && y<p[id].y)) {
        id=i;
    } 
    }
    if(id!=1) swap(p[id],p[1]);
    sort(p+2,p+n+1,cmp);
    que[++ql]=p[1];
    siji(i,2,n) {
    while(ql>=2 && (que[ql]-que[ql-1])*(p[i]-que[ql-1])<=0) --ql;
    que[++ql]=p[i];
    }
    que[ql+1]=p[1];
    int ans=Area()/50;
    printf("%d\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ 2187 Beauty Contest

Description

Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates.
Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.

Input

Line 1: A single integer, N

Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm

Output

Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.

Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

2

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)

题解

这道题是旋转卡壳，我们做一条边的平行线，然后看卡在哪个点上
我们逆时针枚举边，那么最远点也必然是逆时针运动的
然后这道题就从 $O(n^2)$ 优化到了 $O(n)$
既然都是这样，为什么我们不枚举点，非要枚举一条边呢
这个反例可以用一个圆想出来，以某个点为圆心做一个小一点的圆弧，我们会找到圆弧上最后一个点，再找个位置使它离最后一个点距离较小而离中间的某个点距离较远

12.27
依林大哥告诉我我被卡掉了，我去看，还真的被卡掉了
发现我的那个点找的是到直线距离相同时的最后一个，实际上应该找第一个，因为我们可能会错过用第一个点更新的值
反例可以画一个下底边长，上顶边短且非常靠右的梯形
然后我们遍历到上顶边时，就使用第一次更新未使用过的点进行了更新

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double a,double b) {
    return fabs(a-b)<=esp;
}
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend int operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend int dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    int norm() {
    return x*x+y*y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
};
Point p[MAXN];
Point que[MAXN];
int n,id,ql;
bool cmp(Point a,Point b) {
    int delta=(a-p[1])*(b-p[1]);
    if(delta!=0) return delta>0;
    return (a-p[1]).norm()<(b-p[1]).norm();
}
int nxt(int k) {
    if(k==ql) return 1;
    return k+1;
}
void solve() {
    scanf("%d",&n);
    int x,y;
    id=1;
    siji(i,1,n) {
    scanf("%d%d",&x,&y);
    p[i]=Point(x,y);
    if(x<p[id].x || (x==p[id].x && y<p[id].y)) {
        id=i;
    } 
    }
    if(id!=1) swap(p[id],p[1]);
    sort(p+2,p+n+1,cmp);
    que[++ql]=p[1];
    siji(i,2,n) {
    while(ql>=2 && (que[ql]-que[ql-1])*(p[i]-que[ql-1])<=0) --ql;
    que[++ql]=p[i];
    }
    que[ql+1]=que[1];
    int now=3;
    int res=(que[2]-que[1]).norm();
    siji(i,1,ql) {
    while(nxt(now)!=i && (que[i]-que[now])*(que[i+1]-que[now]) <
          (que[i]-que[nxt(now)])*(que[i+1]-que[nxt(now)])) now=nxt(now);
    res=max(res,(que[now]-que[i]).norm());
    res=max(res,(que[now]-que[i+1]).norm());
    }
    printf("%d\n",res);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ 1228 Grandpa's Estate

Description

Being the only living descendant of his grandfather, Kamran the Believer inherited all of the grandpa's belongings. The most valuable one was a piece of convex polygon shaped farm in the grandpa's birth village. The farm was originally separated from the neighboring farms by a thick rope hooked to some spikes (big nails) placed on the boundary of the polygon. But, when Kamran went to visit his farm, he noticed that the rope and some spikes are missing. Your task is to write a program to help Kamran decide whether the boundary of his farm can be exactly determined only by the remaining spikes.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains an integer n (1 <= n <= 1000) which is the number of remaining spikes. Next, there are n lines, one line per spike, each containing a pair of integers which are x and y coordinates of the spike.

Output

There should be one output line per test case containing YES or NO depending on whether the boundary of the farm can be uniquely determined from the input.

Sample Input

1
6
0 0
1 2
3 4
2 0
2 4
5 0

Sample Output

NO

题解

这道题要求这些点确定的凸包大小固定
我们需要每个边上的点至少有三个，这样凸包大小就固定了，否则它还可能扩展
我们就是要求一个凸包，由于卷包裹算法只能求点最少然后涵盖所有点的凸包
虽然这些点都能构成一个凸包，但是不能全部按顺序求出（网上的代码都是错的）
然后我们就求最大的
然后枚举每个点，枚举每个边，看看每条边上有几个点！！！反正 $O(n^2)$ 能过

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double a,double b) {
    return fabs(a-b)<=esp;
}
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend int operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend int dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    int norm() {
    return x*x+y*y;
    }
    bool operator < (const Point &rhs) const {
    return x<rhs.x;
    }
    bool operator ==(const Point &rhs) const {
    return x==rhs.x && y==rhs.y;
    }
};
Point p[MAXN],sta[MAXN];
int top,n;
bool cmp(Point a,Point b) {
    int delta=(a-p[1])*(b-p[1]);
    if(delta!=0) return delta>0;
    return (a-p[1]).norm() < (b-p[1]).norm();    
}
int T;
bool check() {
    siji(i,1,top) {
    int cnt=0;
    siji(j,1,n) {
        if((sta[i]-p[j])*(sta[i+1]-p[j])==0) ++cnt;
    }
    if(cnt<3) return false;
    }
    return true;
}
void solve() {
    scanf("%d",&n);
    int x,y;
    int id=1;
    siji(i,1,n) {
    scanf("%d%d",&x,&y);
    p[i]=Point(x,y);
    if(x<p[id].x || (x==p[id].x && y<p[id].y)) {
        id=i;
    } 
    }
    if(id!=1) swap(p[id],p[1]);
    p[n+1]=p[1];
    top=0;
    sort(p+2,p+n+1,cmp);
    sta[++top]=p[1];
    siji(i,2,n) {
    while(top>=2 && (sta[top]-sta[top-1])*(p[i]-sta[top-1])<=0) --top;
    sta[++top]=p[i];
    }
    if(top<=2) {
    puts("NO");
    return;
    }
    sta[top+1]=p[1];
    if(check()) {
    puts("YES");
    }
    else {
    puts("NO");
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--) {
    solve();
    }
    return 0;
}

BZOJ 1043: [HAOI2008]下落的圆盘

Description

有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红
色线条的总长度即为所求.

Input

第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.

Output

最后的周长，保留三位小数

Sample Input

2
1 0 0
1 1 0

Sample Output

10.472

题解

我们对每个圆求出其他的每个圆覆盖它的角度，然后做线段覆盖，没有覆盖过的地方就累加进答案

重点就是如何求出两个圆覆盖的圆的弧度

想象有一个坐标轴，我们求出两个圆心连线和x轴的夹角，然后用余弦定理求出交点偏转过的两个角度
如果这条圆弧跨过了0，就把这个圆弧拆成左端点到2×pi，0到右端点

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 10005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
bool dcmp(double x,double y) {
    if(fabs(x-y)<esp) return 1;
    else return 0;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x=_x;
        y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
        return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }
    bool operator < (const Point &rhs) const {
        return x<rhs.x;
    }
    bool operator == (const Point &rhs) const {
        return dcmp(x,rhs.x)&&dcmp(y,rhs.y);
    }
    double norm() {
        return sqrt(x*x+y*y);
    }
}p[MAXN];
struct node {
    double ql,qr;
    bool operator < (const node &rhs) const{
        return ql<rhs.ql;
    }
}que[MAXN*10];
double r[MAXN],ans=0.0;
int n,tot;
bool contain(int a,int b) {
    return (p[b]-p[a]).norm()+r[a]<=r[b];
}
void insert(int a,int b) {
    double base,dis,l,t;
    dis=(p[b]-p[a]).norm();
    base=atan2(p[b].x-p[a].x,p[b].y-p[a].y);
    t=(r[a]*r[a]-r[b]*r[b]+dis*dis)/(2*dis*r[a]);
    l=acos(t);
    que[++tot]=(node){base-l,base+l};
}
double calc(int x) {
    tot=0;
    siji(i,x+1,n) {
        if(contain(x,i)) return 0.0;
        else if(!contain(i,x) && (p[i]-p[x]).norm()<=r[i]+r[x]) {
            insert(x,i);
        }
    }
    siji(i,1,tot) {
        if(que[i].ql<0) que[i].ql+=2*pi;
        if(que[i].qr<0) que[i].qr+=2*pi;
        if(que[i].ql>que[i].qr) {
            que[++tot]=(node){0,que[i].qr};
            que[i].qr=2*pi;
        }
    }
    sort(que+1,que+tot+1);
    double last=0.0,tmp=0.0;
    siji(i,1,tot) {
        if(que[i].ql>last) {
            tmp+=que[i].ql-last;
        }
        last=max(last,que[i].qr);
    }
    tmp+=2*pi-last;
    return tmp*r[x];
}
void solve() {
    scanf("%d",&n);
    double x,y;
    siji(i,1,n) {
        scanf("%lf%lf%lf",&r[i],&x,&y);
        p[i]=Point(x,y);
    }
    siji(i,1,n) {
        ans+=calc(i);
    }
    printf("%.3lf\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

BZOJ 1185: [HNOI2007]最小矩形覆盖

给出n，给出n个点
然后求一个面积最小的矩形，输出这个矩形的面积和四个顶点

题解

从前我以为旋转卡壳是一个非常麻烦的东西，还要画很多直线
但是思路其实非常简单，而且代码实现也非常简单，甚至于，它就是一个想法，告诉我们如果逆时针枚举边那么逆时针枚举每个点就能找到离它最远的那个点
然后这道题用到一个……假装是定理吧，我们矩形的一边必须要和凸包的一边重合
然后我们先求凸包，枚举凸包上每条边
然后做一条垂线，找个最靠右的那条边，然后以右边为底边，找左边离它最远的点
最后确定出这个矩形了
然而这道题需要带误差比较
例如我们需要a>=b
我们需要a-b>=-esp

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 50005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
bool dcmp(double a,double b) {
    return fabs(a-b)<=esp;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    friend double dot(const Point &a,const Point &b) {
    return a.x*b.x+a.y*b.y;
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
    bool operator < (const Point &rhs) const {
    return dcmp(y,rhs.y) ? x<rhs.x : y<rhs.y;
    }
    bool operator ==(const Point &rhs) const {
    return x==rhs.x && y==rhs.y;
    }
};
struct line {
    Point a,b;
    line() {}
    line(Point x,Point y) {
    a=x;b=y;
    }
};
Point p[MAXN],sta[MAXN],tmp[5],ansp[5];
line ed[4];
double ans=0.0;
bool cmp(Point a,Point b) {
    double delta=(a-p[1])*(b-p[1]);
    if(!dcmp(delta,0.0)) return delta>0;
    return (a-p[1]).norm()<(b-p[1]).norm();
}
int n,tot;
void init() {
    scanf("%d",&n);
    double x,y;
    int id=1;
    siji(i,1,n) {
    scanf("%lf%lf",&x,&y);
    p[i]=Point(x,y);
    if(p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y)) {
        id=i;
    }
    }
    if(id!=1) swap(p[1],p[id]);
    sort(p+2,p+n+1,cmp);
    sta[++tot]=p[1];
    siji(i,2,n) {
    while(tot>=2 && (sta[tot]-sta[tot-1])*(p[i]-sta[tot-1])<=esp) --tot;
    sta[++tot]=p[i];
    }
    sta[tot+1]=sta[1];
}
int nxt(int k) {
    if(k==tot) return 1;
    else return k+1;
}
double Area(Point l,Point z,Point s) {
    return (l-s)*(z-s);
}
double dist(line l,Point z) {
    double delta=(z-l.a)*(l.b-l.a);
    return delta/(l.b-l.a).norm();
}
Point cross_Point(line l,line z) {
    double d1=dist(l,z.a),d2=dist(l,z.b);
    return z.a+((z.b-z.a)*(d1/(d1-d2)));
}
void solve() {
    init();
    int l=0,r=2,h=3;
    ans=-1.0;
    siji(i,1,tot) {
    while(nxt(h)!=i
          && Area(sta[i],sta[i+1],sta[nxt(h)])-Area(sta[i],sta[i+1],sta[h])>=-esp) h=nxt(h);
    Point t=Point(-(sta[i+1]-sta[i]).y,(sta[i+1]-sta[i]).x);
    while(nxt(r)!=h
          && Area(sta[i]+t,sta[i],sta[nxt(r)])-Area(sta[i]+t,sta[i],sta[r])>=-esp) r=nxt(r);
    if(i==1) l=r;
    while(Area(sta[r],sta[r]+t,sta[nxt(l)])-Area(sta[r],sta[r]+t,sta[l])>=-esp) l=nxt(l);
    ed[0]=line(sta[i],sta[i+1]);
    ed[1]=line(sta[r],sta[r]+t);
    ed[2]=line(sta[h],sta[h]+(sta[i+1]-sta[i]));
    ed[3]=line(sta[l],sta[l]+t);
    siji(i,0,3) {
        tmp[i]=cross_Point(ed[i],ed[(i+1)%4]);
    }
    double L=dist(ed[0],sta[h]),W=dist(ed[1],sta[l]);
    if(L*W<ans || dcmp(ans,-1.0)) {
        ans=L*W;
        memcpy(ansp,tmp,sizeof(tmp));
    }
    }
    int fir=0;
    siji(i,1,3) {
    if(ansp[i]<ansp[fir]) {
        fir=i;
    }
    }
    printf("%.5lf\n",ans);
    siji(i,0,3) {
    printf("%.5lf %.5lf\n",ansp[(fir+i)%4].x,ansp[(fir+i)%4].y);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ2079 Triangle

Description

Given n distinct points on a plane, your task is to find the triangle that have the maximum area, whose vertices are from the given points.

Input

The input consists of several test cases. The first line of each test case contains an integer n, indicating the number of points on the plane. Each of the following n lines contains two integer xi and yi, indicating the ith points. The last line of the input is an integer −1, indicating the end of input, which should not be processed. You may assume that 1 <= n <= 50000 and −104 <= xi, yi <= 104 for all i = 1 . . . n.

Output

For each test case, print a line containing the maximum area, which contains two digits after the decimal point. You may assume that there is always an answer which is greater than zero.

Sample Input

3
3 4
2 6
2 7
5
2 6
3 9
2 0
8 0
6 5
-1

Sample Output

0.50
27.00

题解

旋转卡壳
这道题我们需要考虑一件事，边不一定在凸包上
不过我们需要旋转两个点
枚举i，先旋转i逆时针数第二个，然后再旋转i逆时针数第三个
正确性比较迷啊

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 50005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend int operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    int norm() {
    return x*x+y*y;
    }
};
Point p[MAXN],sta[MAXN];
int ans=0;
bool cmp(Point a,Point b) {
    int delta=(a-p[1])*(b-p[1]);
    if(delta!=0) return delta>0;
    return (a-p[1]).norm()<(b-p[1]).norm();
}
int n,tot;
void init() {
    int x,y;
    int id=1;
    tot=0;
    siji(i,1,n) {
    scanf("%d%d",&x,&y);
    p[i]=Point(x,y);
    if(p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y)) {
        id=i;
    }
    }
    if(id!=1) swap(p[1],p[id]);
    sort(p+2,p+n+1,cmp);
    sta[++tot]=p[1];
    siji(i,2,n) {
    while(tot>=2 && (sta[tot]-sta[tot-1])*(p[i]-sta[tot-1])<=0) --tot;
    sta[++tot]=p[i];
    }
    sta[tot+1]=sta[1];
}
int nxt(int k) {
    if(k==tot) return 1;
    else return k+1;
}
int Area(Point l,Point z,Point s) {
    return (l-s)*(z-s);
}
void solve() {
    init();
    int l=2,z=3;
    ans=0;
    siji(i,1,tot) {
    while(nxt(z)!=i && Area(sta[i],sta[l],sta[z])<=Area(sta[i],sta[l],sta[nxt(z)]))
        z=nxt(z);
    while(nxt(l)!=z && Area(sta[i],sta[l],sta[z])<=Area(sta[i],sta[nxt(l)],sta[z])) 
        l=nxt(l);
    ans=max(ans,Area(sta[i],sta[l],sta[z]));
    }
    printf("%d",ans/2);
    if(ans%2) {
    puts(".50");
    }
    else {
    puts(".00");
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&n)!=EOF) {
    if(n==-1) {
        break;
    }
    solve();
    }
    return 0;
}

代码

半平面交

我点开下一道题之后发现不会……然后发现是半平面交orz
所以先去写了一发板子题

POJ 3335 Rotating Scoreboard

Description

This year, ACM/ICPC World finals will be held in a hall in form of a simple polygon. The coaches and spectators are seated along the edges of the polygon. We want to place a rotating scoreboard somewhere in the hall such that a spectator sitting anywhere on the boundary of the hall can view the scoreboard (i.e., his line of sight is not blocked by a wall). Note that if the line of sight of a spectator is tangent to the polygon boundary (either in a vertex or in an edge), he can still view the scoreboard. You may view spectator's seats as points along the boundary of the simple polygon, and consider the scoreboard as a point as well. Your program is given the corners of the hall (the vertices of the polygon), and must check if there is a location for the scoreboard (a point inside the polygon) such that the scoreboard can be viewed from any point on the edges of the polygon.

Input

The first number in the input line, T is the number of test cases. Each test case is specified on a single line of input in the form n x1 y1 x2 y2 ... xn yn where n (3 ≤ n ≤ 100) is the number of vertices in the polygon, and the pair of integers xi yi sequence specify the vertices of the polygon sorted in order.

Output

The output contains T lines, each corresponding to an input test case in that order. The output line contains either YES or NO depending on whether the scoreboard can be placed inside the hall conforming to the problem conditions.

Sample Input

2
4 0 0 0 1 1 1 1 0
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0

Sample Output

YES
NO

题解

这是一个不规则的多边形，我们要找它的核
我们过每条边做一条线会把这个平面分成两部分，我们把线左边的部分（有向直线）划进我们需要的范围内，然后再对下一条线进行相同的操作
最后剩下的平面交就是我们的答案
这里的顺序是顺时针的

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 1005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
    return Point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
};
struct line {
    Point a,b;
    line() {}
    line(Point _a,Point _b) {
    a=_a;
    b=_b;
    }
};
Point p[MAXN],ans[MAXN],tmp[MAXN];
int T,n,tot,l;
void init() {
    scanf("%d",&n);
    double x,y;
    siji(i,1,n) {
    scanf("%lf%lf",&x,&y);
    p[i]=Point(x,y);
    }
}
double dist(line l,Point s) {
    return (s-l.a)*(l.b-l.a) / (l.b-l.a).norm();
}
Point cross_Point (line l,line z) {
    double d1=dist(l,z.a);
    double d2=dist(l,z.b);
    return z.a+((z.b-z.a)*(d1/(d1-d2)));
}
void solve() {
    init();
    siji(i,1,n) {
        ans[i]=p[i];
    }
    p[n+1]=p[1];
    tot=n;
    ans[tot+1]=ans[1];
    siji(i,1,n) {
        l=0;
        siji(j,1,tot) {
            double t1=(p[i+1]-p[i])*(ans[j]-p[i]);
            double t2=(p[i+1]-p[i])*(ans[j+1]-p[i]);
            if(t1<=0) {
                tmp[++l]=ans[j];
            }
            if(t1*t2<0){
                tmp[++l]=cross_Point(line(p[i],p[i+1]),line(ans[j],ans[j+1]));
            }
        }
        tot=l;
        siji(j,1,tot) {
            ans[j]=tmp[j];
        }
        ans[tot+1]=ans[1];
    }
    if(tot==0) {
    puts("NO");
    }
    else {
    puts("YES");
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--) {
    solve();
    }
    return 0;
}

POJ 3384 Feng Shui

Description

Feng shui is the ancient Chinese practice of placement and arrangement of space to achieve harmony with the environment. George has recently got interested in it, and now wants to apply it to his home and bring harmony to it.
There is a practice which says that bare floor is bad for living area since spiritual energy drains through it, so George purchased two similar round-shaped carpets (feng shui says that straight lines and sharp corners must be avoided). Unfortunately, he is unable to cover the floor entirely since the room has shape of a convex polygon. But he still wants to minimize the uncovered area by selecting the best placing for his carpets, and asks you to help.
You need to place two carpets in the room so that the total area covered by both carpets is maximal possible. The carpets may overlap, but they may not be cut or folded (including cutting or folding along the floor border) — feng shui tells to avoid straight lines.

Input

The first line of the input file contains two integer numbers n and r — the number of corners in George’s room (3 ≤ n ≤ 100) and the radius of the carpets (1 ≤ r ≤ 1000, both carpets have the same radius). The following n lines contain two integers xi and yi each — coordinates of the i-th corner (−1000 ≤ xi, yi ≤ 1000). Coordinates of all corners are different, and adjacent walls of the room are not collinear. The corners are listed in clockwise order.

Output

Write four numbers x1, y1, x2, y2 to the output file, where (x1, y1) and (x2, y2) denote the spots where carpet centers should be placed. Coordinates must be precise up to 4 digits after the decimal point.
If there are multiple optimal placements available, return any of them. The input data guarantees that at least one solution exists.

Sample Input

1

5 2
-2 0
-5 3
0 8
7 3
5 0

2

4 3
0 0
0 8
10 8
10 0

Sample Output

1

-2 3 3 2.5

2

3 5 7 3

题解

这道题半平面交，需要把每条线段向凸包内平移r的长度，然后做半平面交
选择半平面交出的这个凸包距离最远的两个点，然后输出它们的坐标即可
有spj还是很开心的

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 1005
#define esp 1e-8
//#define ivorysi
using namespace std;
typedef long long ll;
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
    x=_x;
    y=_y;
    }
    friend Point operator + (const Point &a,const Point &b) {
    return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    Point operator += (const Point &rhs) {
        return *this=*this+rhs;
    }
    Point operator -= (const Point &rhs) {
        return *this=*this-rhs;
    }
    friend double operator * (const Point &a,const Point &b) {
    return a.x*b.y-a.y*b.x;
    }
    friend Point operator * (const Point &a,const double &b) {
    return Point(a.x*b,a.y*b);
    }
    double norm() {
    return sqrt(x*x+y*y);
    }
};
struct line {
    Point a,b;
    line() {}
    line(Point _a,Point _b) {
        a=_a;
        b=_b;
    }
};
Point p[MAXN],ans[MAXN],tmp[MAXN];
double r;
int T,n,tot,len;
void init() {
    scanf("%d%lf",&n,&r);
    double x,y;
    gongzi(i,n,1) {
        scanf("%lf%lf",&x,&y);
        p[i]=Point(x,y);
    }
}
double dist(line l,Point s) {
    return (s-l.a)*(l.b-l.a) / (l.b-l.a).norm();
}
Point cross_Point (line l,line z) {
    double d1=dist(l,z.a);
    double d2=dist(l,z.b);
    return z.a+((z.b-z.a)*(d1/(d1-d2)));
}
void solve() {
    init();
    siji(i,1,n) {
        ans[i]=p[i];
    }
    p[n+1]=p[1];
    tot=n;
    ans[tot+1]=ans[1];
    siji(i,1,n) {
        len=0;
        Point t=Point(-(p[i+1]-p[i]).y,(p[i+1]-p[i]).x);
        t=t*(r/t.norm());
        p[i]+=t;p[i+1]+=t;
        siji(j,1,tot) {
            double t1=(ans[j]-p[i])*(p[i+1]-p[i]);
            double t2=(ans[j+1]-p[i])*(p[i+1]-p[i]);
            if(t1<=-esp) {
                tmp[++len]=ans[j];
            }
            if(t1*t2 <esp) {
                tmp[++len]=cross_Point(line(p[i],p[i+1]),line(ans[j],ans[j+1]));
            }
        }
        p[i]-=t;p[i+1]-=t;
        tot=len;
        siji(j,1,tot) {
            ans[j]=tmp[j];
        }
        ans[tot+1]=ans[1];
    }
    int r1=1,r2=1;
    double dis=0.0;
    siji(i,1,tot) {
        siji(j,i+1,tot) {
            if((ans[j]-ans[i]).norm()-dis>-esp) {
                r1=i;r2=j;
                dis=(ans[j]-ans[i]).norm();
            }   
        }
    }
    printf("%.6lf %.6lf %.6lf %.6lf\n",ans[r1].x,ans[r1].y,ans[r2].x,ans[r2].y);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}