Pagini recente » Cod sursa (job #1305339) | Cod sursa (job #1690939) | Cod sursa (job #162332) | Cod sursa (job #1683936) | Cod sursa (job #983419)
Cod sursa(job #983419)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
ifstream fin("gold.in");
ofstream fout("gold.out");
const int N = 1040;
typedef pair <int, int> punct;
typedef pair <punct, int> pct;
int sol, n, eps, stot, gold[N];
punct p0, pd, v[N]; pct vo[N];
inline bool cmp(const pct& a, const pct& b)
{
punct p1 = a.first, p2 = b.first;
return ((p1.x-p0.x) * (p2.y-p0.y) - (p2.x-p0.x) * (p1.y-p0.y) > 0);
}
inline bool side(punct p1, punct p2, punct p3)
{
return ((p3.y-p1.y) * (p2.x-p1.x) - (p3.x-p1.x) * (p2.y-p1.y) > 0);
}
inline bool cmp2(const pct& a, const pct& b)
{
punct aa = a.first, bb = b.first;
double r1 = atan2((double)(aa.y - p0.y), (double)(aa.x - p0.x));
double r2 = atan2((double)(bb.y - p0.y), (double)(bb.x - p0.x));
return r1 < r2;
}
void Center(punct p, int poz)
{
p0 = p;
for(int i=1; i<=n; i++) vo[i].first = v[i], vo[i].second = i;
swap(vo[1], vo[poz]);
if(n > 200) sort(vo+2, vo+n+1, cmp);
else sort(vo+2, vo+n+1, cmp2);
int sum = 0, last = 0;
for(int i=3; ; i++)
{
if(i == n+1) i = 2;
if(!side(p, vo[2].first, vo[i].first))
{ last = i; break;}
sum += gold[vo[i].second];
}
//cout<<vo[last].second;
if(abs(stot - sum - gold[poz] - gold[vo[2].second] - sum) <= eps) sol++;
for(int i=3; i<=n; i++)
{
if(sum) sum -= gold[vo[i].second];
//if(sum < 0) sum = 0, last = i+1; if(last == n + 1) last = 2;
if(last == i) last++;
for(int j=last; ; j++)
{
if(j == n + 1) j = 2;
if(!side(p, vo[i].first, vo[j].first))
{ last = j; break;}
sum += gold[vo[j].second];
}
//cout<<sum<<' '<<vo[i].second<<endl;
if(abs(stot - gold[poz] - gold[vo[i].second] - sum - sum) <= eps) sol++;
}
}
int main()
{
fin>>n>>eps;
for(int i=1; i<=n; i++)
fin>>gold[i];
for(int i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
stot += gold[i];
}
for(int i=1; i<=n; i++)
{
Center(v[i], i);
//break;
}
fout<<sol/2;
return 0;
}