杭電ACM-LCY算法進階培訓班-專題訓練（計算幾何入門）

傳送門

• 杭電ACM-LCY算法進階培訓班-專題訓練（計算幾何入門）
• • Shape of HDU
  • • Problem Description
    • Input
    • Output
    • Sample Input
    • Sample Output
    • 代碼
  • 改革春風吹滿地
  • • Problem Description
    • Input
    • Output
    • Sample Input
    • Sample Output
    • 代碼
  • gxx's Problem
  • • Problem Description
    • Input
    • Output
    • Sample Input
    • Sample Output
    • 代碼
  • Surround the Trees
  • • Problem Description
    • Input
    • Output
    • Sample Input
    • Sample Output
    • 代碼
  • 最大三角形
  • • Problem Description
    • Input
    • Output
    • Sample Input
    • Sample Output
    • 代碼

Shape of HDU

Problem Description

話說上回講到海東集團推選老總的事情，最終的結果是XHD以微弱優勢當選，從此以后，“徐隊”的稱呼逐漸被“徐總”所取代，海東集團（HDU）也算是名副其實了。
創業是需要地盤的，HDU向錢江肉絲高新技術開發區申請一塊用地，很快得到了批復，據說這是因為他們公司研發的“海東牌”老鼠藥科技含量很高，預期將占全球一半以上的市場。政府劃撥的這塊用地是一個多邊形，為了描述它，我們用逆時針方向的頂點序列來表示，我們很想了解這塊地的基本情況，現在請你編程判斷HDU的用地是凸多邊形還是凹多邊形呢？

Input

輸入包含多組測試數據，每組數據占2行，首先一行是一個整數n，表示多邊形頂點的個數，然后一行是2×n個整數，表示逆時針順序的n個頂點的坐標（xi,yi），n為0的時候結束輸入。

Output

對于每個測試實例，如果地塊的形狀為凸多邊形，請輸出“convex”,否則輸出”concave”，每個實例的輸出占一行。

Sample Input

4 0 0 1 0 1 1 0 1 0

Sample Output

convex

代碼

#include<cstdio> using namespace std; const int maxn=1e5+5; int n,a[maxn][2];int judge(int i,int j,int k){j%=n,k%=n;int x1=a[j][0]-a[i][0];int y1=a[j][1]-a[i][1];int x2=a[k][0]-a[j][0];int y2=a[k][1]-a[j][1];return x1*y2-x2*y1; }signed main(){while(scanf("%d",&n),n){for(int i=0;i<n;i++)scanf("%d%d",&a[i][0],&a[i][1]);bool flag=true;for(int i=0;i<n;i++)if(judge(i,i+1,i+2)<0){flag=false;break;}if(flag) puts("convex");else puts("concave");} }

改革春風吹滿地

Problem Description

“ 改革春風吹滿地,
不會AC沒關系;
實在不行回老家，
還有一畝三分地。
謝謝!（樂隊奏樂）”

話說部分學生心態極好，每天就知道游戲，這次考試如此簡單的題目，也是云里霧里，而且，還竟然來這么幾句打油詩。
好呀，老師的責任就是幫你解決問題，既然想種田，那就分你一塊。
這塊田位于浙江省溫州市蒼南縣靈溪鎮林家鋪子村，多邊形形狀的一塊地，原本是linle 的，現在就準備送給你了。不過，任何事情都沒有那么簡單，你必須首先告訴我這塊地到底有多少面積，如果回答正確才能真正得到這塊地。
發愁了吧？就是要讓你知道，種地也是需要AC知識的！以后還是好好練吧…

Input

輸入數據包含多個測試實例，每個測試實例占一行，每行的開始是一個整數n(3<=n<=100)，它表示多邊形的邊數（當然也是頂點數），然后是按照逆時針順序給出的n個頂點的坐標（x1, y1, x2, y2… xn, yn）,為了簡化問題，這里的所有坐標都用整數表示。
輸入數據中所有的整數都在32位整數范圍內，n=0表示數據的結束，不做處理。

Output

對于每個測試實例，請輸出對應的多邊形面積，結果精確到小數點后一位小數。
每個實例的輸出占一行。

Sample Input

3 0 0 1 0 0 1 4 1 0 0 1 -1 0 0 -1 0

Sample Output

0.5 2.0

代碼

#include<cstdio> #include<algorithm> using namespace std; const int maxn=105; int n,x[maxn],y[maxn];double calc(int i,int j){if(j>=n) j-=n;return x[i]*y[j]-x[j]*y[i]; }int main(){while(scanf("%d",&n),n){for(int i=0;i<n;i++)scanf("%d%d",&x[i],&y[i]);double ans=0;for(int i=0;i<n;i++)ans+=calc(i,i+1);printf("%.1f\n",abs(ans/2.0));} }

gxx’s Problem

Problem Description

In ACM_DIY, there is a master called “gxx”. Whenever someone asks a problem, he will come out with the Source (such as “in ** OJ, the ID to this problem is **”), then say “The Problem is ShaX……Isn’t it a problem that you should kill in a second? ……” or something like that. One day, one giantarum called ac wants to ask something about the common point(s) of two given “Segments”. Each segment is described as two points in 2D.
Of course, gxx says: “It’s a problem that could be killed in one second!” However, the giantarum ac does not know how to solve this problem, could you help him?

Input

The first line contains one integer T, indicates the number of the test cases. (T <= 100)
Then every case has two lines. Each line has four integer numbers x0 y0 x1 y1, indicates the two end-points of the segment. (0<=|x0|, |y0|, |x1|, |y1| <= 10^6)
All the test cases are seperated by a single blank line.

Output

Output one integer M in a single line, indicates the number of common point(s) of the two given segment.
Then M lines, each line has two fractions in lowest term indicate the common point.
(Of course, if the denominator is one, then you should ignore it!)
Obviously, if lots of points could be found, just output one line “INF”.

Sample Input

5 0 0 1 1 1 0 0 10 0 1 0 1 1 2 20 0 -1 -1 -1 0 0 -10 0 2 2 2 2 4 00 0 1 1 0 0 1 1

Sample Output

1 1/2 1/2 0 1 -1/2 -1/2 1 2 2 INF

代碼

這題并沒有通過。

Surround the Trees

Problem 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

代碼

#include<cstdio> #include<algorithm> #include<stack> #include<cmath> #define int long long using namespace std; const int maxn=5e4+5; int n,a[maxn],p,b,c,x[maxn],y[maxn],s[maxn],tot;bool cmp(int i,int j){if(i==p||j==p) return i==p;return (x[i]-x[p])*(y[j]-y[p])-(x[j]-x[p])*(y[i]-y[p])>0; }double calc(int i,int j,int k){return (x[j]-x[i])*(y[k]-y[j])-(x[k]-x[j])*(y[j]-y[i]); }double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); }signed main(){while(scanf("%lld",&n),n){p=-1;tot=0;for(int i=0;i<n;i++){scanf("%lld%lld",&x[i],&y[i]); a[i]=i;if(p==-1||y[i]<y[p]) p=i;}sort(a,a+n,cmp);s[tot++]=a[0]; s[tot++]=a[1];for(int i=2;i<n;i++){do{c=s[--tot];b=s[tot-1];}while(calc(b,c,a[i]%n)<=0);s[tot++]=c; s[tot++]=a[i];}double ans=0; c=p;do{b=c,c=s[--tot];ans+=dis(b,c);}while(tot);if(n==1) ans=0;else if(n==2) ans=dis(0,1);printf("%.2f\n",ans);} }

最大三角形

Problem Description

老師在計算幾何這門課上給Eddy布置了一道題目，題目是這樣的：給定二維的平面上n個不同的點，要求在這些點里尋找三個點，使他們構成的三角形擁有的面積最大。
Eddy對這道題目百思不得其解，想不通用什么方法來解決，因此他找到了聰明的你，請你幫他解決這個題目。

Input

輸入數據包含多組測試用例，每個測試用例的第一行包含一個整數n，表示一共有n個互不相同的點，接下來的n行每行包含2個整數xi,yi，表示平面上第i個點的x與y坐標。你可以認為：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.

Output

對于每一組測試數據，請輸出構成的最大的三角形的面積，結果保留兩位小數。
每組輸出占一行。

Sample Input

3 3 4 2 6 3 7 6 2 6 3 9 2 0 8 0 6 6 7 7

Sample Output

1.50 27.00

代碼

#include<cstdio> #include<algorithm> #include<stack> #include<cmath> #define int long long using namespace std; const int maxn=5e4+5; int n,a[maxn],p,b,c,x[maxn],y[maxn],s[maxn],tot;bool cmp(int i,int j){if(i==p||j==p) return i==p;return (x[i]-x[p])*(y[j]-y[p])-(x[j]-x[p])*(y[i]-y[p])>0; }double calc(int i,int j,int k){return (x[j]-x[i])*(y[k]-y[j])-(x[k]-x[j])*(y[j]-y[i]); }double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); }signed main(){while(~scanf("%lld",&n)){p=-1;tot=0;for(int i=0;i<n;i++){scanf("%lld%lld",&x[i],&y[i]); a[i]=i;if(p==-1||y[i]<y[p]) p=i;}sort(a,a+n,cmp);for(int i=0;i<n;i++){while(tot>1&&calc(s[tot-2],s[tot-1],a[i])<=0) tot--;s[tot++]=a[i];}double ans=0;for(int i=0;i<tot;i++)for(int j=i+1;j<tot;j++)for(int k=j+1;k<tot;k++)ans=max(ans,calc(s[i],s[j],s[k]));printf("%.2f\n",ans/2.0);} }

總結

以上是生活随笔為你收集整理的杭电ACM-LCY算法进阶培训班-专题训练（计算几何入门）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。