| ||||||||||
| 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