1. 題目列表
- POJ2031（點(diǎn)與點(diǎn)的距離 + 最小生成樹(shù)）
- POJ1039（線段相交判斷，交點(diǎn)的計(jì)算）
- POJ1408（相交線段形成的四邊形面積求解）
- HDU1392（求凸包周長(zhǎng)）
- POJ2187（求任意離散點(diǎn)集中相距最遠(yuǎn)點(diǎn)的距離，凸包 + 旋轉(zhuǎn)卡殼法）
- POJ1113（凸包周長(zhǎng)+定間隔最小包圍周長(zhǎng)）
2. 計(jì)算幾何學(xué)的模板
線段相交：
#include <stdio.h>
#include <math.h>
const int N = 100010;
int mark[N];
struct Point
{
double x,y;
};
struct stline
{
Point a,b;
} line1,line2, p[N];
int dblcmp(double a,double b)
{
if (fabs(a-b)<=1E-6) return 0;
if (a>b) return 1;
else return -1;
}
//***************點(diǎn)積判點(diǎn)是否在線段上***************
double dot(double x1,double y1,double x2,double y2) //點(diǎn)積
{
return x1*x2+y1*y2;
}
int point_on_line(Point a,Point b,Point c) //求a點(diǎn)是不是在線段bc上，>0不在，=0與端點(diǎn)重合，<0在。
{
return dblcmp(dot(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y),0);
}
//**************************************************
double cross(double x1,double y1,double x2,double y2)
{
return x1*y2-x2*y1;
}
double ab_cross_ac(Point a,Point b,Point c) //ab與ac的叉積
{
return cross(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int ab_cross_cd (Point a,Point b,Point c,Point d) //求ab是否與cd相交，交點(diǎn)為p。1規(guī)范相交，0交點(diǎn)是一線段的端點(diǎn)，-1不相交。
{
double s1,s2,s3,s4;
int d1,d2,d3,d4;
Point p;
d1=dblcmp(s1=ab_cross_ac(a,b,c),0);
d2=dblcmp(s2=ab_cross_ac(a,b,d),0);
d3=dblcmp(s3=ab_cross_ac(c,d,a),0);
d4=dblcmp(s4=ab_cross_ac(c,d,b),0);
//如果規(guī)范相交則求交點(diǎn)
if ((d1^d2)==-2 && (d3^d4)==-2)
{
p.x=(c.x*s2-d.x*s1)/(s2-s1);
p.y=(c.y*s2-d.y*s1)/(s2-s1);
return 1;
}
//如果不規(guī)范相交
if (d1==0 && point_on_line(c,a,b)<=0)
{
p=c;
return 0;
}
if (d2==0 && point_on_line(d,a,b)<=0)
{
p=d;
return 0;
}
if (d3==0 && point_on_line(a,c,d)<=0)
{
p=a;
return 0;
}
if (d4==0 && point_on_line(b,c,d)<=0)
{
p=b;
return 0;
}
//如果不相交
return -1;
}
其他：見(jiàn)https://blog.csdn.net/linxilinxilinxi/article/details/82624098
3. POJ1039—Pipe
3.1 題目描述
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.
<center>
</center>
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.
3.2解決思路
題意:
在一個(gè)彎曲的寬度為1的管子中，光從左端射出，求光所能達(dá)到的最大水平距離
長(zhǎng)度。
思路：
最大水平距離的光一定過(guò)某上端點(diǎn)和某下斷點(diǎn)，窮舉所有的上端點(diǎn)和下斷點(diǎn)對(duì)，
即窮舉所有的直線，首先判斷該直線所能到達(dá)的最大管子，然后計(jì)算該直線與該管子
的上壁和下壁的交點(diǎn)，橫坐標(biāo)最大的交點(diǎn)即為光傳播的最大水平距離。
知識(shí)點(diǎn)：
這里涉及到計(jì)算幾何中的利用叉乘計(jì)算線段交點(diǎn)問(wèn)題，應(yīng)熟練的套用模板。
3.3 代碼
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
/*
題意:
在一個(gè)彎曲的寬度為1的管子中，光從左端射出，求光所能達(dá)到的最大水平距離
長(zhǎng)度。
思路：
最大水平距離的光一定過(guò)某上端點(diǎn)和某下斷點(diǎn)，窮舉所有的上端點(diǎn)和下斷點(diǎn)對(duì)，
即窮舉所有的直線，首先判斷該直線所能到達(dá)的最大管子，然后計(jì)算該直線與該管子
的上壁和下壁的交點(diǎn)，橫坐標(biāo)最大的交點(diǎn)即為光傳播的最大水平距離。
知識(shí)點(diǎn)：
這里涉及到計(jì)算幾何中的利用差集計(jì)算線段交點(diǎn)問(wèn)題，應(yīng)熟練的套用模板。
*/
const double eps = 0.001;
const int maxn = 100;
struct Point{
double x, y;
}ups[maxn], downs[maxn];
int dcmp(double d){ // 精度比較
if (fabs(d) < eps)
return 0;
if (d > 0) return 1;
else return -1;
}
double cross(Point a, Point b, Point c){ // 叉乘，計(jì)算ab ×ac
/*
當(dāng)ab ×ac>0時(shí)，說(shuō)明ac在ab的左側(cè)，即點(diǎn)C在ab的左側(cè)
當(dāng)ab ×ac<0時(shí)，說(shuō)明ac在ab的右側(cè)，即C在ab的右側(cè)
當(dāng)ab ×ac=0時(shí)，說(shuō)明點(diǎn)c在線段ab上，即端點(diǎn)相交
*/
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool isIntersect(Point a, Point b, Point c, Point d){ // 判斷直線ab與線段cd是否相交
/*
若點(diǎn)c、d分別在線段ab的兩側(cè)，則一定相交，否則一定不相交
*/
return (dcmp(cross(a, b, c)) * dcmp(cross(a, b, d))) <= 0;
}
double intersection(Point a, Point b, Point c, Point d){
/*
求ab與cd的交點(diǎn)的橫坐標(biāo)
*/
double s1 = cross(a, b, c);
double s2 = cross(a, b, d);
int cc = dcmp(s1);
int dd = dcmp(s2);
if (cc * dd < 0) // 規(guī)范相交
return (s2 * c.x - s1 * d.x) / (s2 - s1); // 交點(diǎn)計(jì)算公式
if (cc * dd == 0){
if (cc == 0) return c.x;
else return d.x;
}
return -1.0;
}
int main(){
int n;
while (~scanf("%d", &n) && n){
for (int i = 1; i <= n; i++){
scanf("%lf%lf", &ups[i].x, &ups[i].y);
downs[i].x = ups[i].x;
downs[i].y = ups[i].y - 1;
}
bool flag = false; // 是否能穿越全部的管子
double MAX = -1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (i == j) continue;
int k;
for (k = 1; k <= n; k++){
// 判斷所能到達(dá)的最大的管子
if (!isIntersect(ups[i], downs[j], ups[k], downs[k])){
break;
}
}
if (k > n){
flag = true;
break;
}
// 計(jì)算上下端點(diǎn)的直線與第maxk-1和maxk個(gè)管子的上交點(diǎn)和下交點(diǎn)的橫坐標(biāo)，取最大值
if (k < max(i, j)) continue; // 如果k比i,j小，則不符合要求
double upx = intersection(ups[i], downs[j], ups[k - 1], ups[k]);
double downx = intersection(ups[i], downs[j], downs[k - 1], downs[k]);
if (upx > MAX) MAX = upx;
if (downx > MAX) MAX = downx;
}
if (flag) break;
}
if (flag) printf("Through all the pipe.\n");
else printf("%.2f\n", MAX);
}
}
4. POJ2031——Building a Space Station
4.1 題目描述
Description
You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write a computer program to complete the task.
The space station is made up with a number of units, called cells. All cells are sphere-shaped, but their sizes are not necessarily uniform. Each cell is fixed at its predetermined position shortly after the station is successfully put into its orbit. It is quite strange that two cells may be touching each other, or even may be overlapping. In an extreme case, a cell may be totally enclosing another one. I do not know how such arrangements are possible.
All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor', or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively.
You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors.
You can ignore the width of a corridor. A corridor is built between points on two cells' surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.
Input
The input consists of multiple data sets. Each data set is given in the following format.
n
x1 y1 z1 r1
x2 y2 z2 r2
...
xn yn zn rn
The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.
The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.
Each of x, y, z and r is positive and is less than 100.0.
The end of the input is indicated by a line containing a zero.
Output
For each data set, the shortest total length of the corridors should be printed, each in a separate line. The printed values should have 3 digits after the decimal point. They may not have an error greater than 0.001.
Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.
Sample Input
3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0
Sample Output
20.000
0.000
73.834
4.2 解決思路
題意：
給定n個(gè)球體，求使其連接的最小連接路徑長(zhǎng)度。
思路：
坐標(biāo)距離計(jì)算 + 最小生成樹(shù)，由于是邊密集問(wèn)題，所以使用Prim算法，
Prim算法與Djkstra算法的唯一區(qū)別是，Prim算法計(jì)算的是點(diǎn)到生成樹(shù)集合
的最短路徑，而Djkstra算法是計(jì)算點(diǎn)到點(diǎn)的最短路徑，因此，在路徑更新時(shí)
Prim算法更新節(jié)點(diǎn)u到集合S的直連距離，而Djkstra算法更新節(jié)點(diǎn)u到源點(diǎn)S的中介距離。
4.3 代碼
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
const double INF = 1e9;
double g[maxn][maxn], x[maxn], y[maxn], z[maxn], r[maxn], d[maxn];
bool visited[maxn];
double Prim(int n){
fill(d, d + maxn, INF);
memset(visited, false, sizeof(visited));
d[1] = 0.0;
double sum = 0.0;
for (int i = 1; i <= n; i++){
int u = -1;
double MIN = INF;
for (int j = 1; j <= n; j++){
if (!visited[j] && d[j] < MIN){
MIN = d[j];
u = j;
}
}
if (u == -1) break;
sum += MIN;
visited[u] = true;
for (int v = 1; v <=n; v++){ // 更新v的直連點(diǎn)到集合S的距離
if (g[u][v] < d[v]) d[v] = g[u][v];
}
}
return sum;
}
int main(){
int n;
while (~scanf("%d", &n) && n){
for (int i = 1; i <= n; i++)
scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++){
if (i == j) g[i][j] = INF;
else{
double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) +
(y[i] - y[j]) * (y[i] - y[j]) +
(z[i] - z[j]) * (z[i] - z[j])
);
g[i][j] = d > (r[i] + r[j]) ? d - (r[i] + r[j]) : 0;
}
}
double res = Prim(n);
printf("%.3f\n", res);
}
}
5. POJ1408——Fishnet
5.1 題目描述
Description
A fisherman named Etadokah awoke in a very small island. He could see calm, beautiful and blue sea around the island. The previous night he had encountered a terrible storm and had reached this uninhabited island. Some wrecks of his ship were spread around him. He found a square wood-frame and a long thread among the wrecks. He had to survive in this island until someone came and saved him.
In order to catch fish, he began to make a kind of fishnet by cutting the long thread into short threads and fixing them at pegs on the square wood-frame. He wanted to know the sizes of the meshes of the fishnet to see whether he could catch small fish as well as large ones.
The wood frame is perfectly square with four thin edges on meter long: a bottom edge, a top edge, a left edge, and a right edge. There are n pegs on each edge, and thus there are 4n pegs in total. The positions of pegs are represented by their (x,y)-coordinates. Those of an example case with n=2 are depicted in figures below. The position of the ith peg on the bottom edge is represented by (ai,0). That on the top edge, on the left edge and on the right edge are represented by (bi,1), (0,ci) and (1,di), respectively. The long thread is cut into 2n threads with appropriate lengths. The threads are strained between (ai,0) and (bi,1),and between (0,ci) and (1,di) (i=1,...,n).
You should write a program that reports the size of the largest mesh among the (n+1)2 meshes of the fishnet made by fixing the threads at the pegs. You may assume that the thread he found is long enough to make the fishnet and the wood-frame is thin enough for neglecting its thickness.
Input
The input consists of multiple sub-problems followed by a line containing a zero that indicates the end of input. Each sub-problem is given in the following format.
n
a1 a2 ... an
b1 b2 ... bn
c1 c2 ... cn
d1 d2 ... dn
you may assume 0 < n <= 30, 0 < ai,bi,ci,di < 1
Output
For each sub-problem, the size of the largest mesh should be printed followed by a new line. Each value should be represented by 6 digits after the decimal point, and it may not have an error greater than 0.000001.
Sample Input
2
0.2000000 0.6000000
0.3000000 0.8000000
0.1000000 0.5000000
0.5000000 0.6000000
2
0.3333330 0.6666670
0.3333330 0.6666670
0.3333330 0.6666670
0.3333330 0.6666670
4
0.2000000 0.4000000 0.6000000 0.8000000
0.1000000 0.5000000 0.6000000 0.9000000
0.2000000 0.4000000 0.6000000 0.8000000
0.1000000 0.5000000 0.6000000 0.9000000
2
0.5138701 0.9476283
0.1717362 0.1757412
0.3086521 0.7022313
0.2264312 0.5345343
1
0.4000000
0.6000000
0.3000000
0.5000000
0
Sample Output
0.215657
0.111112
0.078923
0.279223
0.348958
5.2 解決思路
題意：
在1 ×1正方形中，求由n對(duì)頂點(diǎn)的左右和上下連線所構(gòu)成最大四邊形面積。
思路：
求左右直線和上下直線兩兩的交點(diǎn)，利用叉積計(jì)算四邊形的面積。
5.3 代碼
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
/*
題意：
在1 ×1正方形中，求由n對(duì)頂點(diǎn)的左右和上下連線所構(gòu)成最大四邊形面積。
思路：
求左右直線和上下直線兩兩的交點(diǎn)，利用叉積計(jì)算四邊形的面積。
*/
const int maxn = 35;
const double eps = 0.000001;
double s[maxn][maxn]; // 定義每一塊四邊形的面積
struct Point{
double x, y;
}a[maxn], b[maxn], c[maxn], d[maxn], P, O; // 下上左右頂點(diǎn)的坐標(biāo)，交點(diǎn)和原點(diǎn)坐標(biāo)
int dcmp(double d){
if (fabs(d) < eps) return 0;
if (d > 0) return 1;
else return -1;
}
double cross(Point a, Point b, Point c){ // 叉乘，計(jì)算ab ×ac
/*
當(dāng)ab ×ac>0時(shí)，說(shuō)明ac在ab的左側(cè)，即點(diǎn)C在ab的左側(cè)
當(dāng)ab ×ac<0時(shí)，說(shuō)明ac在ab的右側(cè)，即C在ab的右側(cè)
當(dāng)ab ×ac=0時(shí)，說(shuō)明點(diǎn)c在線段ab上，即端點(diǎn)相交
*/
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
void intersection(Point A, Point B, Point C, Point D, double& x, double& y){
double s1 = cross(A, B, C);
double s2 = cross(A, B, D);
int cc = dcmp(s1);
int dd = dcmp(s2);
if (cc * dd < 0) { // 規(guī)范相交
x = (s2 * C.x - s1 * D.x) / (s2 - s1);
y = (s2 * C.y - s1 * D.y) / (s2 - s1);
}else {
if (cc == 0){
x = C.x;
y = C.y;
}else {
x = D.x;
y= D.y;
}
}
}
int main(){
int n;
while (~scanf("%d", &n) && n){
O.x = O.y = 0;
for (int i = 1; i <= n; i++){
scanf("%lf", &a[i].x);
a[i].y = 0;
}
a[n + 1].x = 1, a[n + 1].y = 0;
for (int i = 1; i <= n; i++){
scanf("%lf", &b[i].x);
b[i].y = 1;
}
b[n + 1].x = 1, b[n + 1].y = 1;
for (int i = 1; i <= n; i++){
scanf("%lf", &c[i].y);
c[i].x = 0;
}
c[n + 1].x = 0, c[n + 1].y = 1;
for (int i = 1; i <= n; i++){
scanf("%lf", &d[i].y);
d[i].x = 1;
}
d[n + 1].x = 1, d[n + 1].y = 1;
double x, y, area, MAX = -1.0; // 交點(diǎn)坐標(biāo)，與坐標(biāo)原點(diǎn)圍成的四邊形面積
fill(s[0], s[0] + maxn * maxn, 0.0);
for (int i = 1; i <= n + 1; i++){
for (int j = 1; j <= n + 1; j++){
intersection(c[i], d[i], a[j], b[j], x, y);
// printf("線段(%lf,%lf)(%lf,%lf)與線段(%lf,%lf)(%lf,%lf)的交點(diǎn)為(%lf,%lf)\n", a[j].x, a[j].y, b[j].x, b[j].y, c[i].x, c[i].y, d[i].x, d[i].y, x, y);
P.x = x, P.y = y;
area = 0.5 * fabs(cross(O, P, a[j])) + 0.5 * fabs(cross(O, P, c[i]));
for (int u = 1; u < i; u++){
for (int v = 1; v <= j; v++)
area -= s[u][v];
}
for (int v = 1; v < j; v++)
area -= s[i][v];
s[i][j] = area;
// printf("第(%d,%d)塊四邊形面積=%lf\n", i, j, area);
if (s[i][j] > MAX) MAX = s[i][j];
}
}
printf("%.6f\n", MAX);
}
}
6. HDU1392——Surround the Trees
6.1 題目描述
Description:
There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.
There are no more than 100 trees.
Input:
The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.
Output:
The minimal length of the rope. The precision should be 10^-2.
Sample Input:
9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0
Sample Output:
243.06
6.2 解決思路
凸包的求解，具體步驟：
1. 求所有點(diǎn)中位于最下方最左的點(diǎn)O；
2. 將所有的點(diǎn)Pi按極角的順序排序，極角為OPi坐標(biāo)的反正切；
3. 利用堆棧數(shù)據(jù)結(jié)構(gòu)，通過(guò)叉乘求解所有在凸包上的點(diǎn)。(畫(huà)圖)
6.3 代碼
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
/*
凸包的求解，具體步驟：
1. 求所有點(diǎn)中位于最下方最左的點(diǎn)O；
2. 將所有的點(diǎn)Pi按極角的順序排序，極角為OPi坐標(biāo)的反正切；
3. 利用堆棧數(shù)據(jù)結(jié)構(gòu)，通過(guò)叉乘求解所有在凸包上的點(diǎn)。(畫(huà)圖)
*/
const int maxn = 110;
const int INF = 1e6;
const double eps = 0.01;
struct Point{
int x, y;
}ps[maxn], s[maxn]; // ps[1]存儲(chǔ)最左下角的點(diǎn)，s為棧
int cross(Point A, Point B, Point C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int cmp(Point A, Point B){
// 按極角大小排序，其中ps[1]為左下角的點(diǎn)
// atan2(y,x)函數(shù)求得是 y/x的反正切
double a = atan2(A.y - ps[1].y, A.x - ps[1].x);
double b = atan2(B.y - ps[1].y, B.x - ps[1].x);
if (a != b) return a < b;
else return A.x < B.x; // 如果極角相同，按橫坐標(biāo)由小到大排序
}
double solve(int n){
// 找到最左下角的點(diǎn)，即最下面的偏左的點(diǎn)
Point min;
min.x = INF, min.y = INF;
int k;
for (int i = 1; i <= n; i++){
if (ps[i].y < min.y || (ps[i].y == min.y) && ps[i].x < min.x){
min = ps[i];
k = i;
}
}
// 將最左下角的點(diǎn)與ps[1]交換
swap(ps[1], ps[k]);
sort(ps + 2, ps + n + 1, cmp); // ps[2]~ps[n]按極角排序
s[0] = ps[1], s[1] = ps[2]; // 初始化棧
int top = 1; // 棧的top指針
for (int i = 3; i <= n;){
if (top && cross(s[top- 1], s[top], ps[i]) <= 0){ // 當(dāng)前棧頂?shù)墓?jié)點(diǎn)不是凸包的節(jié)點(diǎn)，則彈出
top--;
}else{
s[++top] = ps[i++]; // 將p[i]加入凸包中
}
}
double c = 0.0;
for (int i = 0; i < top; i++){
c = c + sqrt((s[i].x - s[i + 1].x) * (s[i].x - s[i + 1].x) + (s[i].y - s[i + 1].y) * (s[i].y - s[i + 1].y));
}
// 首尾相連
c += sqrt((s[top].x - s[0].x) * (s[top].x - s[0].x) + (s[top].y - s[0].y) * (s[top].y - s[0].y));
return c;
}
int main(){
int n;
while (~scanf("%d", &n) && n){
for (int i = 1; i <= n; i++)
scanf("%d%d", &ps[i].x, &ps[i].y);
if (n == 1){
printf("0.00\n");
continue;
}
if (n == 2){
printf("%.2f\n", sqrt((ps[1].x - ps[2].x) * (ps[1].x - ps[2].x) + (ps[1].y - ps[2].y) * (ps[1].y - ps[2].y)));
continue;
}
printf("%.2f\n", solve(n));
}
return 0;
}
7. POJ1584——Beauty Contest
7.1 題目描述
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
OutputLine 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)
7.2 解決思路
旋轉(zhuǎn)卡殼法裸題：
旋轉(zhuǎn)卡殼法的基本原理：對(duì)于凸包上的所有邊，按逆時(shí)針順序枚舉，到邊最遠(yuǎn)的點(diǎn)也是按逆時(shí)針出現(xiàn)，
這樣的話，只需要枚舉完所有的邊，并求最遠(yuǎn)的頂點(diǎn)與邊的兩端點(diǎn)之間的最大距離即可。
時(shí)間復(fù)雜度：
求凸包O(nlogn)，旋轉(zhuǎn)卡殼O(n)，T(n)=O(nlogn)
7.3 代碼
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
/*
旋轉(zhuǎn)卡殼法裸題：
旋轉(zhuǎn)卡殼法的基本原理：對(duì)于凸包上的所有邊，按逆時(shí)針順序枚舉，到邊最遠(yuǎn)的點(diǎn)也是按逆時(shí)針出現(xiàn)，
這樣的話，只需要枚舉完所有的邊，并求最遠(yuǎn)的頂點(diǎn)與邊的兩端點(diǎn)之間的最大距離即可。
時(shí)間復(fù)雜度：
求凸包O(nlogn)，旋轉(zhuǎn)卡殼O(n)，T(n)=O(nlogn)
*/
const int maxn = 50010;
const int INF = 1000000000;
struct Point {
int x, y;
}p[maxn], s[maxn];
int top; // 棧首
int cross(Point A, Point B, Point C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int cmp (Point A, Point B){
double a = atan2(1.0 * (A.y - p[1].y), 1.0 * (A.x - p[1].x));
double b = atan2(1.0 * (B.y - p[1].y), 1.0 * (B.x - p[1].x));
if (a != b) return a < b;
else return A.x < B.x;
}
int getDist(Point A, Point B){
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
void getConvex(int n){
// 找到左下角的點(diǎn)
Point min;
min.x = min.y = INF;
int k;
for (int i = 1; i <= n; i++){
if (p[i].y < min.y || (p[i].y == min.y) && p[i].x < min.x){
min = p[i];
k = i;
}
}
swap(p[1], p[k]);
sort(p + 2, p + n + 1, cmp);
s[0] = p[1], s[1] = p[2], top = 1;
for (int i = 3; i <= n;){
if (top && cross(s[top - 1], s[top], p[i]) <= 0)
top--; // 棧頂?shù)狞c(diǎn)不是凸包的點(diǎn)
else
s[++top] = p[i++];
}
}
int getMaxDist(){
s[++top] = s[0]; // 首尾相連
int MAX = -1;
if (top < 2) return getDist(s[0], s[1]);
// 逆時(shí)針枚舉凸包的所有的邊
int j = 2;
for (int i = 0; i < top; i++){
// 尋找距離邊s[i]s[i+1]最遠(yuǎn)的凸包上的點(diǎn)，根據(jù)叉乘的面積大小判斷
while (cross(s[i], s[i + 1], s[j]) < cross(s[i], s[i + 1], s[j + 1]))
j = (j + 1) % top;
MAX = max(MAX, max(getDist(s[j], s[i]), getDist(s[j], s[i + 1]))); // 取邊的兩個(gè)端點(diǎn)距離最大值
}
return MAX;
}
int main(){
int n;
scanf("%d", &n);
int MAX = -1;
for (int i = 1; i <= n; i++){
scanf("%d%d", &p[i].x, &p[i].y);
}
if (n == 2){
printf("%d\n", getDist(p[1], p[2]));
}else {
getConvex(n);
printf("%d\n", getMaxDist());
}
return 0;
}
8. POJ1113——Wall
7.1 題目描述
Description
Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall.
<center>
</center>
Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King's requirements.
The task is somewhat simplified by the fact, that the King's castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle's vertices in feet.
Input
The first line of the input file contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.
Next N lines describe coordinates of castle's vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.
Output
Write to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King's requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.
Sample Input
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
Sample Output
1628
Hint
結(jié)果四舍五入就可以了
8.2 思路
題意：
給定N個(gè)點(diǎn)，求用一個(gè)周長(zhǎng)最小的多邊形把這些點(diǎn)包進(jìn)去，且每個(gè)點(diǎn)到多邊形的距離都大于等于L。
思路：
先求凸包，對(duì)于每個(gè)頂點(diǎn)X，X的附近需要增加一定的圓弧保證頂點(diǎn)到圓弧的
距離大于等于L，而所有X的圓弧角度之和為PI，將凸包平移與圓弧連接成封閉
圖案，最終ans=凸包周長(zhǎng)+2*PI*L
8.3 代碼
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
const int INF = 0x7fffffff;
const double eps = 0.75;
const double pi = acos(-1.0);
struct Point {
int x, y;
}p[maxn], s[maxn];
int top;
int dcmp(double a, double b){
if (fabs(a - b) < eps) return 0;
if (a > b) return 1;
else return -1;
}
int cmp(Point A, Point B){
double a = atan2(1.0 * (A.y - p[1].y), 1.0 * (A.x - p[1].x));
double b = atan2(1.0 * (B.y - p[1].y), 1.0 * (B.x - p[1].x));
if (a != b) return a < b;
else return A.x < B.x;
}
int cross(Point A, Point B, Point C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
double dot(Point A, Point B, Point C, Point D){ // AB ·CD
return (B.x - A.x) * (D.x - C.x) + (B.y - A.y) * (D.y - C.y);
}
void getConvex(int n){
Point min;
min.x = min.y = INF;
int k;
for (int i = 1; i <= n; i++)
if (p[i].y < min.y || (p[i].y == min.y) && p[i].x < min.x){
min = p[i];
k = i;
}
swap(p[1], p[k]);
sort(p + 2, p + n + 1, cmp);
s[0] = p[1], s[1] = p[2], top = 1;
for (int i = 3; i <= n;){
if (top && cross(s[top - 1], s[top], p[i]) <= 0)
top--;
else
s[++top] = p[i++];
}
}
double getDist(Point A, Point B){
return sqrt(1.0 * (A.x - B.x) * (A.x - B.x) + 1.0 * (A.y - B.y) * (A.y - B.y));
}
double getAngle(Point A, Point B, Point C, Point D){
// 返回AB與CD向量夾角的弧度
return fabs(acos(dot(A, B, C, D) / (getDist(A, B) * getDist(C, D))));
}
double solve(int L){
if (top == 1) return (getDist(s[0], s[1]));
s[++top] = s[0];
double c = 0.0;
// 枚舉所有的邊
// c += getDist(s[0], s[1]);
// if (cross(s[top - 1], s[0], s[1]) != 0){
// double theta = getAngle(s[top - 1], s[0], s[0], s[1]);
// c += theta * L;
// }
for (int i = 0; i < top; i++){
c += getDist(s[i], s[i + 1]);
// if (cross(s[i - 1], s[i], s[i + 1]) != 0){ // 不在一條直線上
//
// double theta = getAngle(s[i - 1], s[i], s[i], s[i + 1]);
// c += (theta * L);
// }
}
c += 2 * pi * L;
return c;
}
int Round(double d){
return floor(d + 0.5);
}
int main(){
int n, L;
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
getConvex(n);
double res = solve(L);
// printf("%lf\n", res);
printf("%d\n", Round(res));
return 0;
}
