C11TRCNT – spoj

Đề bài:

Thuật toán:

  • Bài toán đưa về: kiểm tra 3 điểm có thẳng hàng hay không

Code:

const   fi='';
        fo='';
type    dinh=record
                x,y:longint;
                end;
var     i,j,k:integer;
        d,max,min:int64;
        kq,n:byte;
        p:array[1..200] of dinh;
        dem:array[1..200] of int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do readln(f,p[i].x,p[i].y);
    close(f);
end;
function kt(x1,y1,x2,y2,x3,y3:longint):boolean;
begin
        if x1*y3-x1*y2+x2*y1-x2*y3+x3*y2-x3*y1=0
        then exit(false) else exit(true);
end;
procedure xuly;
begin
    d:=0; min:=1000000000000000;
    for i:=1 to n do
    begin
        for j:=1 to n do
        if i<>j then
                for k:=1 to n do
                if (i<>k) and (j<>k) then
                                if kt(p[i].x,p[i].y,p[j].x,p[j].y,p[k].x,p[k].y)  then
                                begin
                                        inc(dem[i]);
                                        if (i<j) and (k>j) then inc(d);
                                end;
        if dem[i]<min then begin min:=dem[i]; kq:=i; end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,d,' ',kq);
    close(f);
end;
begin
    nhap;
    xuly;
    inkq;
end.
Khuyên dùng

 

Speak Your Mind

*