2014-01-03 - HIR180's diary

■ JOI 2007 Lines 13:21

定数倍嫌いわかる
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1e8
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
int v[1000005]={};
int main()
{
	int n;
	P a[1005],b[1005];
	mapint>point;
	setlines;
	scanf("%d",&n);
	for(int i=0;i"%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
ll x=x2-x1,y=y2-y1;
		if(x1==x2)
		{
			a[i]=mp(INF,INF);
			b[i].first=x1;
			lines.insert(mp(a[i],b[i]));
		}
		else
		{
			ll d=__gcd(abs(y),abs(x));
			a[i]=mp(y/d,x/d);
			if(a[i].second<0) {a[i].first=0-a[i].first; a[i].second=0-a[i].second;}
 
			ll as=x2*y1-x1*y2;
			d=__gcd(abs(as),abs(x));
			b[i]=mp(as/d,x/d);
			if(b[i].second<0) {b[i].first=0-b[i].first; b[i].second=0-b[i].second;}
			lines.insert(mp(a[i],b[i]));
		}
	}
	vectorvec;
	set::iterator it;
	for(it=lines.begin();it!=lines.end();++it)
	{
		vec.pb(*it);
	}
	n=vec.size();
	int ret=n+1;
	for(int i=0;ifor(int j=i+1;jif(a1==a2) continue;
			if(a1.first==INF)
			{
				ll x=a2.first*b1.first*b2.second+a2.second*b2.first;
				ll y=a2.second*b2.second;
				
				ll d=__gcd(abs(x),abs(y));
				P s=mp(x/d,y/d);
				if(s.second<0){ s.first=0-s.first; s.second=0-s.second;}
				point[mp(mp(b1.first,1),s)]++; continue;
			}
			if(a2.first==INF)
			{
				ll x=a1.first*b2.first*b1.second+a1.second*b1.first;
				ll y=a1.second*b1.second;
 
				ll d=__gcd(abs(x),abs(y));
				P s=mp(x/d,y/d);
				if(s.second<0){ s.first=0-s.first; s.second=0-s.second;}
				point[mp(mp(b2.first,1),s)]++;continue;
			}
			
			{
			
				ll up=(b2.first*b1.second-b1.first*b2.second)*a1.second*a2.second;
				ll down=(a1.first*a2.second-a2.first*a1.second)*b2.second*b1.second;
				ll d=__gcd(abs(up),abs(down));
				up/=d; down/=d;
				if(down<0){ up=0-up; down=0-down;}
				ll up2=(a1.first*up*b1.second+b1.first*a1.second*down);
				ll down2=a1.second*down*b1.second;
				d=__gcd(abs(up2),abs(down2));
				up2/=d; down2/=d;
				if(down2<0){ up2=0-up2; down2=0-down2;}
				point[mp(mp(up,down),mp(up2,down2))]++;
			}
		}
	}
	mapint>::iterator itt;
	vector<int>val;
	for(int i=1;i<=1000;i++)
	{
		v[i*(i+1)/2]=i;
	}
	for(itt=point.begin();itt!=point.end();++itt)
	{
		int f=v[itt->second];
		ret+=f;
	}
	printf("%d\n",ret);
}