首爾性愛美術館18禁的藝術6檔好股票放一年賺5成這畫面也太叫人垂涎欲滴!睽違25天終開會 立院...
2012-03-16 11:39:27 人氣(253) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][ConvexHull] 218 - Moth Eradication

0
收藏
0
推薦

 Moth Eradication 

Entomologists in the Northeast have set out traps to determine the influx of Jolliet moths into the area. They plan to study eradication programs that have some potential to control the spread of the moth population.

The study calls for organizing the traps in which moths have been caught into compact regions, which will then be used to test each eradication program. A region is defined as the polygon with the minimum length perimeter that can enclose all traps within that region. For example, the traps (represented by dots) of a particular region and its associated polygon are illustrated below.

You must write a program that can take as input the locations of traps in a region and output the locations of traps that lie on the perimeter of the region as well as the length of the perimeter.

Input

The input file will contain records of data for several regions. The first line of each record contains the number (an integer) of traps for that region. Subsequent lines of the record contain 2 real numbers that are the x- and y-coordinates of the trap locations. Data within a single record willnot be duplicated. End of input is indicated by a region with 0 traps.

Output

Output for a single region is displayed on at least 3 lines:

tabular26

One blank line must separate output from consecutive input records.

Sample Input

31 24 105 12.360 01 13.1 1.33 4.56 2.12 -3.271 0.55 04 1.53 -0.22.5 -1.50 02 20

Sample Output

Region #1:(1.0,2.0)-(4.0,10.0)-(5.0,12.3)-(1.0,2.0)Perimeter length = 22.10Region #2:(0.0,0.0)-(3.0,4.5)-(6.0,2.1)-(2.0,-3.2)-(0.0,0.0)Perimeter length = 19.66Region #3:(0.0,0.0)-(2.0,2.0)-(4.0,1.5)-(5.0,0.0)-(2.5,-1.5)-(0.0,0.0)Perimeter length = 12.52


順時針的凸包輸出, 接著計算凸包的邊長


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
float x, y;
}Point;
Point P[100000], CH[100000];
int cmp(const void *i, const void *j) {
Point *a, *b;
a = (Point *)i, b = (Point *)j;
if(a->x != b->x)
return a->x - b->x > 0 ? 1 : -1;
return a->y - b->y > 0 ? 1 : -1;
}
double cross(Point o, Point a, Point b) {
return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
int montoneChain(int n) {
qsort(P, n, sizeof(Point), cmp);
int i, j, m = 0;
for(i = 0; i < n; i++) {
while(m >= 2 && cross(CH[m-2], CH[m-1], P[i]) >= 0)
m--;
CH[m++] = P[i];
}
for(i = n-1, j = m+1; i >= 0; i--) {
while(m >= j && cross(CH[m-2], CH[m-1], P[i]) >= 0)
m--;
CH[m++] = P[i];
}
float length = 0;
for(i = 0; i < m; i++) {
if(i) {
printf("-");
length += sqrt((CH[i].x-CH[i-1].x)*(CH[i].x-CH[i-1].x) +
(CH[i].y-CH[i-1].y)*(CH[i].y-CH[i-1].y));
}
printf("(%.1f,%.1f)", CH[i].x, CH[i].y);
}
puts("");
printf("Perimeter length = %.2f\n", length);
}
int main() {
int n, i, Case = 0;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%f %f", &P[i].x, &P[i].y);
if(Case) puts("");
printf("Region #%d:\n", ++Case);
montoneChain(n);
}
return 0;
}

218Moth Eradication
台長:Morris
人氣(253) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][BFS] 572 - Oil Deposits
此分類上一篇:[UVA] 10922 - 2 the 9s

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文