Submission #633359

#	Time	Username	Problem	Language	Result	Execution time	Memory
633359		andrei_boaca	Printed Circuit Board (CEOI12_circuit)	C++14	20 / 100	1089 ms	6764 KiB

circuit

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
    ll x,y,ang,poz;
} v[100005];
bool byang(int q, int t)
{
    point a=v[q];
    point b=v[t];
    if(a.y*b.x!=a.x*b.y)
        return a.y*b.x<a.x*b.y;
    return a.x<b.x;
}
bool iseq(point A, point B)
{
    return A.x==B.x&&A.y==B.y;
}
int intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 1;

    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<=C.x&&y<=C.y&&x>0&&y>0)
        return 1;
    if(x==0&&y==0)
        return -1;
    return 0;
}
bool bylin(int q,int t)
{
    point a=v[q];
    int nxt=q+1;
    if(nxt>n)
        nxt=1;
    point b=v[nxt];

    point c=v[t];
    nxt=t+1;
    if(nxt>n)
        nxt=1;
    point d=v[nxt];

    int isC=intersect(a,b,c);
    int isD=intersect(a,b,d);
    if(isC==0&&isD==0)
        return 0;
    if(isC==1&&isD==1)
        return 1;

    int isA=intersect(c,d,a);
    int isB=intersect(c,d,b);
    if(isA==0&&isB==0)
        return 1;
    if(isA==1&&isB==1)
        return 0;
    return 0;
}
int fst[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].poz=i;
    }
    vector<int> ind;
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),byang);
    int nr=0;
    for(int i=0;i<ind.size();i++)
    {
        if(i==0)
            nr++;
        else
        {
            point a=v[ind[i-1]];
            point b=v[ind[i]];
            if(a.y*b.x!=a.x*b.y)
                nr++;
        }
        v[ind[i]].ang=nr;
    }
    ind.clear();
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),bylin);
    for(int i:ind)
    {
        int st=v[i].ang;
        int nxt=i+1;
        if(nxt>n)
            nxt=1;
        int dr=v[nxt].ang;
        if(st>dr)
            swap(st,dr);
        for(int j=st;j<=dr;j++)
            if(fst[j]==0)
                fst[j]=i;
    }
    vector<int> sol;
    for(int i=1;i<=n;i++)
    {
        int ang=v[i].ang;
        //cout<<fst[ang]<<' ';
        int prv=i-1;
        if(i==1)
            prv=n;
        if(fst[ang]!=i&&fst[ang]!=prv)
            continue;
        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 'int intersect(point, point, point)':
circuit.cpp:34:8: warning: unused variable 'c2' [-Wunused-variable]
   34 |     ll c2=0;
      |        ^~
circuit.cpp: In function 'int main()':
circuit.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<ind.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 20 / 100