Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
简单题n^2水过对于每条线段,按照斜率排序,对于横线和竖线特判即可 #include <cstdio> #include <algorithm> struct L{ int dx,dy; }line[41000]; int n,x[210],y[210],lz; bool fx,fy; int gcd(int x,int y){ if (!y) return x; else return gcd(y,x%y); } bool cmp(L a,L b){ double x1=a.dx,x2=b.dx,y1=a.dy,y2=b.dy; double k1=x1/y1,k2=x2/y2; return k1<k2; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); lz=fx=fy=0; for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++){ lz++; line[lz].dx=x[j]-x[i]; line[lz].dy=y[j]-y[i]; if (line[lz].dx<0) line[lz].dx=-line[lz].dx,line[lz].dy=-line[lz].dy; if (!line[lz].dx||!line[lz].dy){ lz--; if (!line[lz+1].dx&&!line[lz+1].dy) continue; if (!line[lz+1].dx) fx=1; if (!line[lz+1].dy) fy=1; continue; } int g=gcd(line[lz].dx,abs(line[lz].dy)); line[lz].dx/=g; line[lz].dy/=g; } std::sort(line+1,line+lz+1,cmp); int ans=fx+fy+1; for (int i=2;i<=lz;i++) if (line[i].dx!=line[i-1].dx||line[i].dy!=line[i-1].dy) ans++; printf("%d",ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator