Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define maxn 1005
- bool visited[maxn];
- ll dx[8]={0,0,1,-1,1,1,-1,-1};
- ll dy[8]={1,-1,0,0,1,-1,1,-1};
- struct cap{
- ll x;
- ll y;
- } aa[maxn];
- bool check(cap a, cap b, cap c){
- ll x1,y1,x2,y2,x3,y3;
- x1=a.x ; y1=a.y;
- x2=b.x ; y2=b.y;
- x3=c.x ; y3=c.y;
- if((x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)) return true;
- // ll res = x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);
- // if(res==0) return true;
- return false;
- }
- int main(){
- // freopen("input.inp","r",stdin);
- // freopen("output.out","w",stdout);
- ll n,x0,y0;
- cin>>n>>x0>>y0;
- cap goc;
- goc.x=x0;
- goc.y=y0;
- ll i;
- for(i=0;i<n;i++){
- cin>>aa[i].x>>aa[i].y;
- }
- ll ans=0;
- ll dem;
- for(i=0;i<n;i++){
- if(visited[i]) continue;
- visited[i]=true;
- dem=1;
- for(ll j=0;j<n;j++){
- if(i==j) continue;
- if(visited[j]==false){
- if(check(goc,aa[i],aa[j])){
- visited[j]=true;
- }
- }
- }
- ans+=dem;
- }
- cout<<ans;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét