Bài toán
Cho một tập hợp các đoạn thẳng, hỏi có bao nhiêu cách vẽ một tam giác sao cho hợp ba cạnh của tam giác là tập con của hợp các đoạn thẳng, hay nói cách khác là không có điểm nào trên ba cạnh tam giác không nằm trên các đoạn thẳng ban đầu.
Độ phức tạp
chưa xác định
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
#define long long long
typedef pair<long, long> llll;
typedef pair<llll, long> line;
typedef pair<llll, llll> segm;
typedef pair<llll, llll> LLLL;
#define X first
#define Y second
llll minimize(llll u){
long GCD = __gcd(abs(u.X), abs(u.Y));
if (u<llll()) GCD = -GCD;
u.X/=GCD, u.Y/=GCD;
return u;
}
bool operator <= (long A, llll B){ B=minimize(B); return A*B.Y <= B.X; }
bool operator >= (long A, llll B){ B=minimize(B); return A*B.Y >= B.X; }
bool operator == (long A, llll B){ B=minimize(B); return A*B.Y == B.X; }
bool operator <= (llll A, LLLL B){ return A.X==B.X ? A.Y<=B.Y : A.X<=B.X; }
bool operator >= (llll A, LLLL B){ return A.X==B.X ? A.Y>=B.Y : A.X>=B.X; }
bool operator == (llll A, LLLL B){ return A.X==B.X ? A.Y==B.Y : A.X==B.X; }
llll xxfu(llll A, llll B){ return llll(B.X-A.X, B.Y-A.Y); }
llll fn(llll u){ return llll(-u.Y, u.X); }
line xxfd(llll A, llll B){ llll n = fn(xxfu(A, B)); return line(n, n.X*A.X+n.Y*A.Y); }
bool in_order(llll A, LLLL B, llll C){
if (A<=B && C>=B) return true;
if (A>=B && C<=B) return true;
return false;
}
bool colinear(llll A, llll B, llll C){
if (A==B || B==C || C==A) return true;
llll uAB = minimize(xxfu(A,B));
llll uAC = minimize(xxfu(A,C));
return uAB==uAC;
}
int n;
segm e[12309];
bool join(segm AB, segm CD, segm& AD){
if (!colinear(AB.X, AB.Y, CD.X)) return false;
if (!colinear(AB.X, AB.Y, CD.Y)) return false;
AD.X = max(min(AB.X, AB.Y), min(CD.X, CD.Y));
AD.Y = min(max(AB.X, AB.Y), max(CD.X, CD.Y));
if (AD.X>AD.Y) return false;
AD.X = min(min(AB.X, AB.Y), min(CD.X, CD.Y));
AD.Y = max(max(AB.X, AB.Y), max(CD.X, CD.Y));
return true;
}
void join(){
bool ok=false;
segm zz;
int i, j;
while (!ok){
ok=true;
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
if (join(e[i], e[j], zz))
{ e[i]=zz; swap(e[j], e[n--]); ok=false; }
}
}
bool try_ddfx(line u, line v, LLLL &A){
long D = u.X.X*v.X.Y-u.X.Y*v.X.X;
if (D==0) return false;
long DX = u.Y*v.X.Y-u.X.Y*v.Y;
long DY = u.X.X*v.Y-u.Y*v.X.X;
A.X = minimize(llll(DX, D));
A.Y = minimize(llll(DY, D));
return true;
}
bool try_DDfx(segm AB, segm AC, LLLL &A){
line dAB = xxfd(AB.X, AB.Y);
line dAC = xxfd(AC.X, AC.Y);
if (!try_ddfx(dAB, dAC, A)) return false;
if (!in_order(AB.X, A, AB.Y)) return false;
if (!in_order(AC.X, A, AC.Y)) return false;
return true;
}
bool ok(segm AB, segm AC, segm BC){
LLLL A, B, C;
if (!try_DDfx(AB, AC, A)) return false;
if (!try_DDfx(AB, BC, B)) return false;
if (!try_DDfx(BC, AC, C)) return false;
if (A==B || B==C || C==A) return false;
return true;
}
main(){
int i, j, k;
int answer=0;
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%lld%lld%lld%lld", &e[i].X.X, &e[i].X.Y, &e[i].Y.X, &e[i].Y.Y);
join();
//for (i=1; i<=n; i++)
//printf("%lld %lld %lld %lld\n", e[i].X.X, e[i].X.Y, e[i].Y.X, e[i].Y.Y);
for (i=1; i<=n-2; i++)
for (j=i+1; j<=n; j++)
for (k=j+1; k<=n; k++)
if (ok(e[i], e[j], e[k]))
answer ++;
printf("%d\n", answer);
}
Nhận xét