Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #212 - PRAVO (sort và chặt nhị phân, không dùng hình học)
Ngày: 27-05-2011
Cập nhật: 04-09-2012
Người gửi: hunterphu
Ngôn ngữ: C++
Xem: 754

Điểm: 4.6/5 (19 Phiếu)


/*
Với mỗi đỉnh i có n-1 vector chỉ phương (x,y) có gốc là i, trường hợp x=0 hoặc y=0 xét riêng (trong bài là x0,y0)
res:=0
Với vector i(xi,yi) cần đếm số lượng vector j = vector i ( xj=xi và yj=yi), giả sử là k
Đếm số lượng vector = vector(-yi,xi) là p, res+=k*p
Đếm số lượng vector = vector(yi,-xi) là q, res+=k*q
*/
 
#include<iostream>
#define nm 1510
using namespace std;
struct node
{
       int x,y;
       node (){}
       node (int c1,int c2)
       {
            x=c1,y=c2;
       }
       bool operator < (node D)const
       {
            if (x!=D.x)
               return x<D.x;
            return y<D.y;
       }
};
 
void hieuchinh(int&u,int&v);
int gcd(int a,int b);
int flx(int x,int l,int r);
int frx(int x,int l,int r);
int fly(int x,int l,int r);
int fry(int x,int l,int r);
 
int n,m,u,v,res;
int x0,y0;
int l,r,ll,rr;
node a[nm];
node dt[nm];
 
int main()
{
    scanf ("%d",&n);
    for (int i=1;i<=n;i++)
        scanf ("%d%d",&a[i].x,&a[i].y);
    for (int i=1;i<=n;i++)
    {
        m=x0=y0=0;
        for (int j=1;j<=n;j++)
        if (i!=j)
        {
            u=a[j].x-a[i].x;
            v=a[j].y-a[i].y;
            hieuchinh(u,v);
            if (u!=0&&v!=0)
               dt[++m]=node(u,v);
            else if (!u) y0++;
                 else if (!v) x0++;
        }
        res+=x0*y0;// các vector có x=0 hoặc y=0
        sort(dt+1,dt+m+1);
        for (int j=1;j<=m;j++)
        if (dt[j].x>0)break;
        else
        {
            l=j;
            r=frx(dt[j].x,1,m);
            if (l<=r)
            {
               ll=j;
               rr=fry(dt[j].y,l,r);
               //Đã được xoá :D
               if (ll<=rr)
               {
                  x0=rr-ll+1;
                  l=flx(-dt[j].y,1,m);
                  r=frx(-dt[j].y,1,m);
                  if (l<=r)
                  {
                     ll=fly(dt[j].x,l,r);
                     rr=fry(dt[j].x,l,r);
                     if (ll<=rr)
                        res+=(rr-ll+1)*x0;
                  }
                  l=flx(dt[j].y,1,m);
                  r=frx(dt[j].y,1,m);
                  if (l<=r)
                  {
                     ll=fly(-dt[j].x,l,r);
                     rr=fry(-dt[j].x,l,r);
                     if (ll<=rr)
                        res+=(rr-ll+1)*x0;
                  }
               }
               //Đã được xoá :P
            }
        }
    }
    printf ("%d",res);
    return 0;
}
 
void hieuchinh(int&u,int&v)
{
     if (!u||!v)return;
     if (v<0)u=-u,v=-v;
     int temp=gcd(abs(u),abs(v));
     u/=temp;
     v/=temp;
 
}
int gcd(int a,int b)
{
    if (!b)return a;
    return gcd(b,a%b);
}
int flx(int x,int l,int r)
{
    while (l<=r)
    {
          int mid=(l+r)/2;
          if (dt[mid].x>=x)
             r=mid-1;
          else l=mid+1;
    }
    return l;
}
int frx(int x,int l,int r)
{
    while (l<=r)
    {
          int mid=(l+r)/2;
          if (dt[mid].x<=x)
             l=mid+1;
          else r=mid-1;
    }
    return r;
}
int fly(int x,int l,int r)
{
    while (l<=r)
    {
          int mid=(l+r)/2;
          if (dt[mid].y>=x)
             r=mid-1;
          else l=mid+1;
    }
    return l;
}
int fry(int x,int l,int r)
{
    while (l<=r)
    {
          int mid=(l+r)/2;
          if (dt[mid].y<=x)
             l=mid+1;
          else r=mid-1;
    }
    return r;
}