| ||||||||||
| 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