凸包问题.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

//凸包问题
/*
输入
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;
}