Submission #632507

#	Time	Username	Problem	Language	Result	Execution time	Memory
632507		andrei_boaca	Printed Circuit Board (CEOI12_circuit)	C++14	10 / 100	1090 ms	10076 KiB

circuit

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
    ll x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].ang!=v[b].ang)
        return v[a].ang<v[b].ang;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int cur=0;
bool iseq(point a, point b)
{
    return a.x==b.x&&a.y==b.y;
}
ll aria(point A, point B)
{
    ll rez=1LL*A.x*B.y-1LL*A.y*B.x;
    return rez;
}
bool intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 0;

    ll a1=B.y-A.y;
    ll b1=A.x-B.x;
    ll c1=-a1*A.x-b1*A.y;

    ll a2=C.y;
    ll b2=-C.x;
    ll c2=0;

    ld coef=a2*b1-a1*b2;
    if(coef==0)
        return 0;
    ld y=ld(-a2*c1)/coef;
    ld x=ld(-b2*y)/a2;
    if(x>=min(A.x,B.x)&&x<=max(A.x,B.x)&&x<=C.x&&x>=0)
        if(y>=min(A.y,B.y)&&y<=max(A.y,B.y)&&y<=C.y&&y>=0)
            return 1;
    return 0;
}
bool checkgood(int i)
{
    if(cur==0)
        return 1;
    point a=v[cur];
    int lft=cur-1;
    if(lft<1)
        lft=n;
    point b=v[lft];
    if(intersect(a,b,v[i]))
        return 0;
    int rgt=cur+1;
    if(rgt>n)
        rgt=1;
    b=v[rgt];
    if(intersect(a,b,v[i]))
        return 0;
    return 1;
}
vector<int> sol;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    /*sort(angle+1,angle+n+1,comp);
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }*/
    for(int i=1;i<=n;i++)
    {
        bool ok=1;
        for(int j=1;j<=n&&ok;j++)
            {
                int nxt=j+1;
                if(j==n)
                    nxt=1;
                if(j!=i&&nxt!=i)
                    if(intersect(v[j],v[nxt],v[i]))
                        ok=0;
            }
        if(ok)
            sol.push_back(i);
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Compilation message (stderr)

circuit.cpp: In function 'bool intersect(point, point, point)':
circuit.cpp:62:8: warning: unused variable 'c2' [-Wunused-variable]
   62 |     ll c2=0;
      |        ^~

• Subtask 1: 10 / 100