3174.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3174  User Id:fzk 
Memory:88K  Time:92MS
Language:C++  Result:Accepted

Source 

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

////////////////////////////////
typedef int Type;/*坐标类型*/
////////////////////////////////

//点的定义
struct point
{
	Type x,y;
	int id;
	point(){x=y=0;}
	point(Type x,Type y):x(x),y(y){;}
	bool operator==(point &a){return x==a.x&&y==a.y;}
};
//叉乘
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}

//点乘
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}


point o;
bool cmp( point &a, point &b ) {
	return cheng( o, a, b ) < 0;
}

point p[770];
point q[770];

int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}

vector<int> v;

int main( ) {
	int i, j, k, n, m, a, b;
	int s[3];
	
	scanf( "%d", &n );

	for( i=0; i<n; i++ ) {
		scanf( "%d%d", &p[i].x, &p[i].y );
		p[i].id = i+1;
	}

	sort( p, n );

	for( i=0; i<n; i++ ) {
		for( j=i+1; j<n; j++ )
			q[j-i-1] = p[j];
		
		m = n-i-1;
		o = p[i];

		sort( q, q+m, cmp );

		for( j=0; j<m; j=k ) {
			for( k=j+1; k<m && cheng( o, q[j], q[k] ) == 0; k++ )
				;
			if( k - j >= 2 ) {
				for( a = j; a<k; a++ )
					for( b = a+1; b<k; b++ ) {
						s[0] = o.id;
						s[1] = q[a].id;
						s[2] = q[b].id;
						sort( s, s+3 );
						v.push_back( (s[0]<<20) | (s[1]<<10) | s[2] );
					}
			}
		}
	}

	sort( v.begin(), v.end() );

	printf( "%d\n", v.size() );
	for( i=0; i<v.size(); i++ ) {
		printf( "%d %d %d\n", v[i]>>20, (v[i]>>10)&1023, v[i]&1023 );
	}
	return 0;
}