poj 1809 Regetni-組合せ数学
11409 ワード
A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2 Try to make clever use of this formula.
最初はどう考えても見当がつかず、後でdiscussをちらっと見たが、実は各点の座標は2のモジュールにしか意味がないという人がいた.ちょっと考えがある
合計メソッド数はC(n,3)であり,さらに満たされない場合の
変形:y 1*(x 3-x 2)+y 2*(x 1-x 3)+y 3*(x 2-x 1)
状況を満たさないのは奇+奇+奇......(1)
奇+偶+偶......(2)
(1)式をxで整理すると,偶+偶+偶となり,成り立たない
(2)4つの不満をまとめる:
(0,0) (0,1) (1,0)
(0,0) (0,1) (1,1)
(0,0) (1,0) (1,1)
(0,1) (1,0) (1,1)
問題全体をo(n)の複雑さに変えた~~~~
a27400
1809
Accepted
620K
79MS
G++
852B
2011-09-15 21:56:00
最初はどう考えても見当がつかず、後でdiscussをちらっと見たが、実は各点の座標は2のモジュールにしか意味がないという人がいた.ちょっと考えがある
合計メソッド数はC(n,3)であり,さらに満たされない場合の
変形:y 1*(x 3-x 2)+y 2*(x 1-x 3)+y 3*(x 2-x 1)
状況を満たさないのは奇+奇+奇......(1)
奇+偶+偶......(2)
(1)式をxで整理すると,偶+偶+偶となり,成り立たない
(2)4つの不満をまとめる:
(0,0) (0,1) (1,0)
(0,0) (0,1) (1,1)
(0,0) (1,0) (1,1)
(0,1) (1,0) (1,1)
問題全体をo(n)の複雑さに変えた~~~~
a27400
1809
Accepted
620K
79MS
G++
852B
2011-09-15 21:56:00
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
long long map[5][5];
long long point[10010][3];
inline long long cal(long long n)
{
return n*(n-1)*(n-2)/6;
}
int main(void)
{
int T;
scanf("%d",&T);
int cas;
for(cas=1;cas<=T;cas++)
{
memset(map,0,sizeof(map));
printf("Scenario #%d:
",cas);
long long n;
scanf("%lld",&n);
int i;
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&point[i][0],&point[i][1]);
point[i][0]=(point[i][0]+100000)%2;
point[i][1]=(point[i][1]+100000)%2;
map[point[i][0]][point[i][1]]++;
}
long long total=cal(n);
total-=map[0][0]*map[0][1]*map[1][0];
total-=map[0][0]*map[0][1]*map[1][1];
total-=map[0][0]*map[1][0]*map[1][1];
total-=map[0][1]*map[1][0]*map[1][1];
printf("%lld
",total);
}
return 0;
}