Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
又是大水题一个#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator