Cod sursa(job #1925696)

Utilizator enedumitruene dumitru enedumitru Data 13 martie 2017 16:22:18
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define Dmax 100005
#define x first
#define y second
#define pa pair <double, double>
using namespace std;
ifstream f("nori.in"); ofstream g("nori.out");
int n,m;
pa p[Dmax],q[Dmax];
struct art {double rap; int poz,ef;} t[Dmax];
double eps=0.00000000000000001;
int cmp(pa A, pa B)
{   if(A.x+eps<B.x) return 1;
    if(B.x+eps<A.x) return 0;
    if(A.y+eps<B.y) return 1;
    if(B.y+eps<A.y) return 0;
    return 1;
}
int cmp1(art A, art B)
{   return A.rap+eps<B.rap;}
int cmp2(art A, art B)
{   return A.poz<B.poz;}
int main()
{   f>>n;
    for(int a,b,r,i=1;i<=n;i++)
    {   f>>a>>b>>r;
        double c=a*a+b*b-r*r;
        p[i].x=(b*c-a*r*sqrt(c))/(a*c+b*r*sqrt(c));
        p[i].y=(b*c+a*r*sqrt(c))/(a*c-b*r*sqrt(c));
    }
    sort(p+1,p+n+1,cmp);
    int k=1;
    q[1]=p[1];
    for(int i=2;i<=n;)
        if(p[i].y+eps<q[k].y) i++;
        else
        {   if(q[k].y+eps<p[i].x) q[++k]=p[i];
            else q[k].y=p[i].y;
            i++;
        }
    f>>m;
    for(int a,b,j=1;j<=m;j++) {f>>a>>b; t[j].rap=(double)b/a; t[j].poz=j;}
    sort(t+1,t+m+1,cmp1);
    int i=1,j=1;
    while(i<=k and j<=m)
        if(t[j].rap+eps<q[i].x) {t[j].ef=1; j++;}
        else if(t[j].rap+eps<q[i].y) {t[j].ef=0; j++;} else i++;
    while(j<=m) {t[j].ef=1; j++;}
    sort(t+1,t+m+1,cmp2);
    for(int j=1;j<=m;j++) g<<t[j].ef;
    g.close();
    return 0;
}