?? 凸包問(wèn)題.txt
字號(hào):
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
//凸包問(wèn)題
/*
輸入
6
0 0
4 0
2 1
0 4
3 4
1 7
*/
#define NMAX 11
int x[NMAX];
int y[NMAX];
int tb[NMAX];
bool cal(double a,double b,double c,double s1,double s2,int num)
{ //直線方程
int i,flag,begin=-1;
for(i=0;i<num;i++)
{
if(i!=s1&&i!=s2)
{
if(a*x[i]+b*y[i]<c) flag=1;
else flag=0;
if(begin==-1) begin=flag;
if(flag!=begin) return false;
}
}
return true;
}
void tubao(int num)
{
int i,j;
for(i=0;i<num-1;i++)
{
for(j=i+1;j<num;j++)
{
if(cal(y[j]-y[i],x[i]-x[j],x[i]*y[j]-x[j]*y[i],i,j,num))
tb[i]=tb[j]=1;
}
}
}
int main()
{
int num,i;
scanf("%d",&num);
for(i=0;i<num;i++)
scanf("%d%d",&x[i],&y[i]);
tubao(num);
for(i=0;i<num;i++)
if(tb[i]==1) cout<<i+1<<" ";
cout<<endl;
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -