Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

又是大水题一个

Posted by KatrineYang at 2016-11-14 13:51:38 on Problem 1569
#include <stdio.h>
#include <string.h>

struct PT{
	int x,y;
	char label;
};
typedef struct PT pt;
pt points[30];

struct triangle{
	pt *p1, *p2, *p3;
};
typedef struct triangle sgx;

int area2(sgx* s){
	int res = (s->p3->y-s->p1->y)*(s->p2->x-s->p1->x);
	res -= (s->p2->y-s->p1->y)*(s->p3->x-s->p1->x);
	return (res<0)? -res: res;
}

int rx(pt* p1, pt* p2, pt* p3){
	int r = p1->x*p2->y+p2->x*p3->y+p3->x*p1->y;
	r -= p1->y*p2->x+p2->y*p3->x+p3->y*p1->x;
	return r;
}

int neiMian(sgx* s, pt* p){
	int rx1 = rx(s->p1, p, s->p2);
	int rx2 = rx(s->p2, p, s->p3);
	int rx3 = rx(s->p3, p, s->p1);
	if((rx1>=0 && rx2>=0 && rx3>=0) || (rx1<=0 && rx2<=0 && rx3<=0)) return 1;
	return 0;
}

void print(sgx* s){
	char label[5];
	label[0] = s->p1->label, label[1] = s->p2->label, label[2] = s->p3->label;
	label[3] = '\0';
	st(label, 3);
	printf("%s\n", label);
}

int main(int argc, char **argv){
	while(1){
		int n;
		scanf("%d",&n);
		if(n<=0) break;
		for(int i = 0; i < n; i++){
			char t[4];
			scanf("%s",t);
			points[i].label = t[0];
			scanf("%d%d",&points[i].x, &points[i].y);
		}
		int mA = 0;
		sgx SGX;
		for(int i = 0; i < n-2; i++){
			for(int j = i+1; j < n-1; j++){
				for(int k = j+1; k < n; k++){
					sgx ijk;
					ijk.p1 = &points[i];
					ijk.p2 = &points[j];
					ijk.p3 = &points[k];
					int kx = 1;
					for(int l = 0; l < n; l++){
						if(l==i || l==j || l==k) continue;
						if(neiMian(&ijk, &points[l])){
							kx = 0; break;
						}
					}
					if(kx){
						int A = area2(&ijk);
						if(A>mA){
							mA=A;
							SGX=ijk;
						}
					}
				}
			}
		}
		print(&SGX);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator