Thứ Sáu, 6 tháng 11, 2020

Kiểm tra ba điểm thằng hàng và duyệt trâu

 Đề bài:$\href{http://codeforces.com/contest/514/problem/B}{Đây}$

Tóm tắt: Cho $n\le 1000$ điểm trên mặt phẳng. Và một điểm gốc A. Hỏi cần ít nhất bao nhiêu đường thẳng đi qua A và đi qua n điểm trên.

Lời giải:

+ Kiểm tra 3 điểm thẳng hàng và duyệt trâu.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 1005
  5. bool visited[maxn];
  6. ll dx[8]={0,0,1,-1,1,1,-1,-1};
  7. ll dy[8]={1,-1,0,0,1,-1,1,-1};
  8. struct cap{
  9. ll x;
  10. ll y;
  11. } aa[maxn];
  12. bool check(cap a, cap b, cap c){
  13. ll x1,y1,x2,y2,x3,y3;
  14. x1=a.x ; y1=a.y;
  15. x2=b.x ; y2=b.y;
  16. x3=c.x ; y3=c.y;
  17. if((x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)) return true;
  18. // ll res = x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);
  19. // if(res==0) return true;
  20. return false;
  21. }
  22. int main(){
  23. // freopen("input.inp","r",stdin);
  24. // freopen("output.out","w",stdout);
  25. ll n,x0,y0;
  26. cin>>n>>x0>>y0;
  27. cap goc;
  28. goc.x=x0;
  29. goc.y=y0;
  30. ll i;
  31. for(i=0;i<n;i++){
  32. cin>>aa[i].x>>aa[i].y;
  33. }
  34. ll ans=0;
  35. ll dem;
  36. for(i=0;i<n;i++){
  37. if(visited[i]) continue;
  38. visited[i]=true;
  39. dem=1;
  40. for(ll j=0;j<n;j++){
  41. if(i==j) continue;
  42. if(visited[j]==false){
  43. if(check(goc,aa[i],aa[j])){
  44. visited[j]=true;
  45. }
  46. }
  47. }
  48. ans+=dem;
  49. }
  50. cout<<ans;
  51. return 0;
  52. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...